-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEuler015.java
More file actions
executable file
·46 lines (39 loc) · 1.32 KB
/
Copy pathEuler015.java
File metadata and controls
executable file
·46 lines (39 loc) · 1.32 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.math.BigInteger;
import java.util.Date;
/*
Project Euler Problem 15
========================
Starting in the top left corner of a 2 * 2 grid, there are 6 routes
(without backtracking) to the bottom right corner.
How many routes are there through a 20 * 20 grid?
*/
public class Euler015 {
public static void main(String[] args) {
Date start, end;
start = new Date();
BigInteger solution = choose(40, 20);
end = new Date();
System.out.println("There are " + solution + " routes");
System.out.println("Executuion Time: " + (end.getTime()-start.getTime()));
}
public static BigInteger factorial(int n) {
BigInteger fact = new BigInteger("1");
for (int i = 1; i <= n; i++) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
public static BigInteger choose(int n1, int n2){
BigInteger l = new BigInteger("1");
int top, bottom;
top = ((n1-n2) > n1/2 ? n2 : n1-n2);
bottom = ((n1-n2) > n1/2 ? n1-n2 : n2);
for(int i = n1; i > top; i--){
l = l.multiply(new BigInteger(Integer.toString(i)));
}
for(int i = bottom; i > 0; i--){
l = l.divide(new BigInteger(Integer.toString(i)));
}
return l;
}
}