## Amazon Interview Question

Software Engineer / DevelopersIf N is Even x = N/2

If N is odd X = N/2-1

Answer is :

Xc0+Xc1+Xc2....+Xcx

Correct me if my answer is wrong.

Guys!!!

who ever not willing to accept fibonacci series as answer, try to use mathematical induction and you'll get the answer as Fibonacci series.....

already at step-1 : hence if n=1 , no.of ways=1

if n=2, already at step-1: hence only 1 way possible hence-> 1

n=3 (1,1) or (2) -> 2 ways

f(3)=f(2)+f(1);

...............n=4,5,6,....please try out

Fibonacci is the correct solution.

But the defination should be as below:

f(n) = f(n-1) + f(n-2) +1

f(1) = 0

f(2) = 1

F(4) should be equal to 3 bt the above formula is giving 4. There are 3 ways

1->2->3->4

1->2->4

1->3->4.

I think fib is correct. This is the simple observation:

- hi guys September 01, 2010Let f(i) be the number of ways that can be taken to reach step i.

f(2) = 1

f(i) = f(i-1) + f(i-2)

That is, if we assume that we are about to take the last step for reaching i, either we are at step i-1 or at step i-2. Coming to step (i-1) we could have taken f(i-1) ways, for coming to i-2, we could have taken f(i-2) different ways.