**Find Paths** — Puzzle for Interview rounds

# Question :

Consider a rectangular grid of 4×3 with lower left corner named as A and upper right corner named B. Suppose that starting point is A and you can move one step up(U) or one step right(R) only. This is continued until B is reached.

How many different paths from A to B possible ?

# Solution :

Could you solve it?

**The correct answer is 10.**

Let’s solve it. Let’s have a look at some sample paths we can figure out by inspection.(R = Right one unit, U = Up one unit)

RRRUU;

UURRR;

RURUR;

RRUUR; and so on.

Could you analyse by having a look on them that every good route consists

of 5 moves and we have 3 R moves and 2 U moves?

We can use this to generalize a formula to find the number of possible routes. Since as we’ve shown, order does not matter in our paths (we can have an R in any place of our 5 moves),

we can use our combination formula: **C(N,R) = N!/(N-R)! * R!**

The number of how many good routes we have can be found by finding how many combinations of 3 R’s we can have in our 5 moves, so we want to calculate:

**C(5,3) = 5!/(5–3)! * 2! = 10**