Labels

Project Euler #15: Lattice paths

Question: 

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?

Hacker Rank Problem 


 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
import java.util.*;
import java.math.*;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int m = in.nextInt();
            int n = in.nextInt();

            BigInteger Required = factorial(BigInteger.valueOf(n+m)) .divide(factorial(BigInteger.valueOf(n))) .divide(factorial(BigInteger.valueOf(m))) .mod((BigInteger.valueOf(1000000007)));
            System.out.println(Required.toString());


        }
    }

    static BigInteger factorial(BigInteger n)
    {
        if (n == BigInteger.ZERO)
            return BigInteger.ONE;

        return n.multiply(factorial(n.subtract(BigInteger.ONE )));
    }
}
Labels:

Comments

Post a Comment

Popular Posts