You are living in the world of 2d graphs. You start at point (0,0). Your friends' house is at coordinates (10,10).You can only move either one step RIGHT or one step UP at a time. Can you find number of ways to reach your friends house?
Well if you said 20C10 then why not. Since it is just a way to arrange 10 ups and 10 rights in an array and whatever combination you get defines a path to (0,0) to (10,10).
Easy?Hmm.Well the tricky(or is it?) part is, can you calculate the number of ways to reach the same destination if you have to make only even number of turns in your journey?
What is a turn exactly? Suppose my path is RUR then you took as many turns as the changes in consecutive elements in the sequence which will be 2 turns. Now since we want to make even number of turns suppose we start with UP direction, then what should be the last direction in our path?? UP right? So first and last directions should be the same. Now for the remaining path we can actually take any possible decision to go UP or RIGHT. Since suppose you make odd number of turns in the middle sequence, then first and last directions will be different which will mean that exactly one turn will get added when we consider first and last element also. Similarly if even number of turns are made, then either 0 or 2 turns will be added after considering first and last elements. So the answer to the puzzle is 2*18C10
Got asked this question in an interview, so I thought i would share it here ^_^