Sunday, October 3, 2010

Count the number of ways .

Lets start with a simple but a tricky one :)

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.
Find the number of ways in which your friend can take all the chocolates in any number of times.

Approach :


The first thing to note is that how can you take n chocolates ?
Before having n chocolates you need to have either n-1 or n-2 chocolates (as you can only pick 1 or 2 chocolates).

So if f(n) denotes the number of ways to pick n chocolates then
f(n) = f(n-1) + f(n-2)
Wow it turns out to be a Fibonacci series !!!
Base cases you can work it out  :)

Try the extension of this problem here

4 comments :

  1. int no_of_ways(int total_coins)
    {
    if(0==total_coins ||1==total_coins||2==total_coins) return total_coins;
    return (no_of_ways(total_coins-1) + no_of_ways(total_coins-2) );
    }

    ReplyDelete
  2. In simple terms.... it is a Fibonacci series :)

    ReplyDelete
  3. sir,
    ek dum hit nahi howz it fibonacci
    shashwat sinha

    ReplyDelete
  4. It can be understood if u look at the problem as a DP. Since u can give only 1 or 2 chocolates at a time so the number of ways can be computed based on the earlier computations. If
    Number of ways of giving n chocolates = f(n)
    So f(n) = f(n-1) + f(n-2) which is a Fibonacci series.

    Regards

    ReplyDelete