# Finding points in a grid with exactly k paths to them?

Suppose that we begin at (0, 0) and are allowed to take two types of steps - steps one unit up and steps one unit to the right. For example, a legal path might be (0, 0) → (1, 0) → (2, 0) → (2, 1) → (3, 1).

Now, suppose that you are given a number k. Is there an efficient algorithm to list of all points (x, y) with exactly k paths to them? For example, given the number 6, we would list (1, 5), (5, 1) and (2, 2), since these points have exactly six paths to them.

Thanks!

-

## migrated from stackoverflow.comJan 30 '12 at 21:27

This question came from our site for professional and enthusiast programmers.

you may refer stackoverflow.com/questions/58306/… –  qiao Jan 29 '12 at 5:56
Do you want the number of paths, or all possible total paths? –  templatetypedef Jan 29 '12 at 6:03
I edited your question because by your example seems you looking for pair of points. –  Saeed Jan 29 '12 at 10:26
If you start at (0,0), I get that you have 15 possible paths to (4,2), and 7 possible paths to (6,1) or have I misunderstood the question...? –  Pedery Jan 29 '12 at 10:28
This shouldnt be allowed ! its Facebook Hacker Cup Q1) Checkpoint... and the contest in not over yet ! –  Pheonix Jan 29 '12 at 13:42

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);
}
}
}
}

-
What value of MAX are you using here? How does it pertain to the choice of the value of k? Also, is there a method that's more efficient than this O(k^2) approach? –  templatetypedef Jan 29 '12 at 7:18
But this method looks promising.. If there is any other method with less complexity it would be better. But if you make a Pascal Matrix out of it then the coordinates are just the (row,column) number of the matrix. en.wikipedia.org/wiki/Pascal_matrix –  Android Decoded Jan 29 '12 at 7:25
But if suppose the distinct path is given as 100000 or so.. then it would be difficult to go by this method –  Android Decoded Jan 29 '12 at 7:29
Yes, MAX can't exceed k (cause any cells that is up-righter that specific cell have more variants to be achieved). Complexity is actually O(K^1.5), cause every next line we can build not till j = k, but we can stop if we got value more than k (in this case values right to those cell will be bigger), so we'll stop at row ceil(sqrt(k)) due to symmetry. –  OleGG Jan 29 '12 at 7:47
So, complexity O(k^1.5) will be still good until one million. We have good constant in O notation - cause we only sum up some integers. –  OleGG Jan 29 '12 at 7:52

This sounds to me like a combinatorial problem.

Say you start in (x, y) and want to go to (x+3, y+3). If we represent all "up" movements by 'U' and all "right" movements by 'R', such a path could be UUURRR. The total number of possible paths would be all possible permutations of UUURRR, namely 6!/(3!3!) = 20.

An algorithm finding all these paths could be to put all 'U's and 'R's in a pool and select one from the pool. This will be your first move. Then find all permutations involving the rest of the pool. Finally swap your first choice (i.e. an 'U') for the opposite choice (this time an 'R') and do it again. Recursively you'll now have found all possible paths between the two points.

Did you read my entire answer? If there are R right moves and U up moves between two points, then all paths leading between them will number C(R+U, R) (using binomial notation). Thus one will need to iterate over i and j to find all of them that result in i!/((i-j)!j!)=n. From there one can use my proposition in the second last paragraph to calculate the actual paths, given that you now know the steps that can take you there (but not the order). –  Pedery Jan 29 '12 at 13:34