Hackerrank – Problem description
The problem description – Hackerrank.
Solution
The solution is based on this article.
I created solution in:
All solutions are also available on my GitHub profile.
Java
|
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 47 48 49 50 |
import java.math.BigInteger; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class LatticePaths { // http://www.robertdickau.com/lattices.html public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); for (int i = 0; i < tests; i++) { String[] numbers = scanner.nextLine().split("\\s+"); int n = Integer.parseInt(numbers[0]); int m = Integer.parseInt(numbers[1]); Set<Integer> nFactorialMembers = new HashSet<>(); for (int j = 1; j <= n; j++) { nFactorialMembers.add(j); } Set<Integer> mFactorialMembers = new HashSet<>(); for (int j = 1; j <= m; j++) { mFactorialMembers.add(j); } Set<Integer> mnFactorialMembers = new HashSet<>(); for (int j = 1; j <= m + n; j++) { mnFactorialMembers.add(j); } // (m+n) chose m === (m+n)!/m!n! // divided n! mnFactorialMembers.removeAll(nFactorialMembers); BigInteger result = BigInteger.ONE; for (Integer k : mnFactorialMembers) { result = result.multiply(new BigInteger(k.toString())); } for (Integer k : mFactorialMembers) { result = result.divide(new BigInteger(k.toString())); } System.out.println(result.mod(new BigInteger("1000000007"))); } scanner.close(); } } |