Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

**Running time:** 0ms

**Assessment:** I was totally lost on this problem, and I eventually had to search for some clue as to how to solve it. Once I learned it was an n-choose-k problem, it was a lot easier. I used the simplified binomial coefficient algorithm described in the Wikipedia article, but only after making sure I understood what was going on and why it was used.

This simplified method ensures you don’t overflow your primitives when calculating factorials, and it’s ridiculously fast. (As I recall, it’s much faster than the ideal solution posted by the project admins.)

In retrospect, it seems obvious that it’s a combinatorics problem, because you can’t go backwards or up, but that wasn’t apparent to me when I started.

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 |
public class Problem015 { public static long binomialCoefficient(int n, int k) { /* N-choose-k combinatorics: (n! / (k! * (n-k)!) * Where: * n is the number of moves, * k is the number of down and right moves required (20 each) */ if (k > (n-k)) k = n - k; long c = 1; for (int i = 0; i < k; i++) { c = c * (n-i); c = c / (i+1); } return c; } public static void main (String[] args) { long begin = System.currentTimeMillis(); System.out.println(binomialCoefficient(40,20)); long end = System.currentTimeMillis(); System.out.println(end-begin + "ms"); } } |

Hi ,

For 22 grid , u r answer wont give 6 as the answer.

For 32 grid also the solution , is bad.

How does this problem became the Combinatorics problem , please explain.