We can use dynamic programming to find those paths. Note, that all points (X, 0) and (0, Y) have only one path to achieve them, because we must go only up or only right to came to this point. Also, if we know number of paths to (I-1, J) and (I, J-1) we can assume that value for (I, J) will be sum of this values - we can make last step to the right, or to the up.
for (int i = 0; i <= MAX; ++i) { paths[i][0] = paths[0][i] = 1; } for (int i = 1; i <= MAX; ++i) { for (int j = 1; j <= MAX; ++j) { paths[i][j] = paths[i-1][j] + paths[i][j-1]; } }
If you print out values in this table, you can find that this is Pascal's triangle, so you can try to find efficient algorithm to finding those numbers in this construction.
Note that you don't need all table paths[][]
, but only previous and current rows. Also, due to symmetry, you can count values only when I < J, so if (I, J) is accessible in k number of ways, same number of ways will stay for (J, I).
EDIT: new solution with optimized speed and memory consumption:
int MAX = 10000000; int[] pathPrev = new int[MAX + 1]; int[] pathCurr = new int[MAX + 1]; for (int i = 0; i <= MAX; ++i) { pathCurr[i] = 1; } for (int i = 1; i * i <= MAX; ++i) { int[] temp = pathPrev; pathPrev = pathCurr; pathCurr = temp; pathCurr[0] = 1; for (int j = 1; pathCurr[j-1] < MAX; ++j) { pathCurr[j] = pathCurr[j-1] + pathPrev[j]; if (pathCurr[j] == MAX && i <= j) { System.out.println(i + " " + j); if (i != j) { System.out.println(j + " " + i); } } } }