CareerCup

for n=1, its one way
for n=2, its 2 ways
for n=3, its 3 ways
for n=4, its 5 ways
for n=5, its 8 ways
for n=6, its 13 ways, so on

It is a fibonacci series...
f(n) = f(n-1) + f(n-2)

It is the Fibolasic Problem F(n)=F(n-1)+F(n-2)

here is nice post on this question
campuscoke.blogspot.in/2014/12/given-n-stairs-how-many-number-of-ways.html

The solution is analogous to the linear equation in 2 variable.
a+2b=n, n known, 0<a<=n, 0<b<=n/2
a can take (n+1) places, b can take (n/2+1)
Total cases = (n+1) * (n/2+1)

Please comment

to reach on floor it may go with one step or two step , so person has to choices.

lets take small example. if person wants to reach on 5th floor from ground then how many ways he can reach.

to reach ground to first floor - 2 ways ( one step or two step )
to reach first to second floor - 2 ways ( one step or two step )
to reach second to third floor - 2 ways ( one step or two step )
to reach third to forth floor - 2 ways ( one step or two step )
to reach forth to five floor - 2 ways ( one step or two step )

to total way = 2*2*2*2*2
similar case for n = 2*2*2......n = 2 power of n

Hi Deepak,
But check the case with reaching 3rd floor:
you have only 3 cases:
first, take all one steps
second, take a one step initially and followed by a two step
third, take a two step initially and followed by a one step

thats all...
Please correct me if am wrong..

it's 2 to the power of (n - 1). To get to the 3 rd floor from the first floor you need 4 ways

Well, I am not sure if I am reading too much in the question, but it says N floors and not N steps. So to get to the 1st floor, either you can take 1 or 2 steps, so you would require X: 1 steps and Y: 2 steps.. so to get to the Nth floor you need NX + NY steps and Y steps = 2X thus, you need 3NX steps or 1.5NY steps... i duno.. please correct me if I am wrong..

Dear Sn,

If you require X number of 1-steps and Y number of 2-steps ,
then Y < X .
Hence, X = 2Y
So, to reach the nth floor, you need 3NY or 1.5NX steps.

This is a permutation / combination problem. (rather only permutation)...We need to find the number of ways to reach the nth floor with 1 or 2 steps at a time.

So, if n=6, we can have
1 + 1 + 1 + ...
1 + 2 + 1 + ... and so on..

Draw a tree and u could see that at each level, there is a node for either 2 or 1. Chk the current sum at each node. Its hence a recursive program with the following DS;

struct StepNode
{
int curr_sum;
int *arr // if they want the type of combinations
};

Number of integral solution for the below mention Linear Equation in two variable
a+2b=n, n known, 0<a<=n, 0<b<=n/2
a= n-2b; (1)
n >= n-2b >=0 implies 0<=b<=n/2
Total Integral solution for (1) equation is
(n-2b+1-1)C(1-1) = n-2b;
Now, b varies from 0 to n/2
Summation : i = 0 to n/2 , n-2i
n*(n+2)/2 - n(n+2)/4 = n*(n+2)/2

Number of integral solution for the below mention Linear Equation in two variable
a+2b=n, n known, 0<a<=n, 0<b<=n/2
a= n-2b; (1)
n >= n-2b >=0 implies 0<=b<=n/2
Total Integral solution for (1) equation is
(n-2b+1-1)C(1-1) = n-2b;
Now, b varies from 0 to n/2
Summation : i = 0 to n/2 , n-2i
n*(n+2)/2 - n(n+2)/4 = n*(n+2)/4

DP :

step(n)
{
1 + max(step(n-1),step(n-2))
}

As per the question, we are required to find out TOTAL NUMBER OF DIFFERENT WAYS to reach from 1st floor to Nth Floor. We are not calculating the total number of STEPs needed to reach the Nth floor. Hence this question becomes a permutation & combination problem.

The correct answer should be power(2, n-1). "Deepak Garg" has explained it and "Anonymous" has corrected it.

Solutions (a+2b = n) and fibonacci numbers are not correct.

Fibonacci Number Solution :

From Floor 1 to Floor 3 :
a. (1,1,1)
b. (1,2)
c. (2,1)

Total number of ways is 3. In this solution, only (a) is correct. In (b) & (c) we are not even traversing 3 floors.

Hence solutin of fibonacci numbers does not work.

We can come up with similar arguments for linear equation solution.

power(2, n-1) fails.
Say n = 4
the possible combinations are
1234
134
124
234
24
power(2, n-1) gives you 8

What I understand from the problem stmt, to reach 1 floor if there are 'm' steps, person can take 1 or 2 steps at a time to reach 1st floor. Thus for 'n' floors, there are total 'nm' steps. If a person takes 1 step throughout, then he will be climbing 'nm' steps to reach nth floor, while if he takes 2 steps at a time, he will have to climb 'nm/2' steps. Thus total no. of ways to climb nth floor are 'nm - nm/2' = 'nm/2'.
Correct me if I am wrong.

well somebody here needs to check their algorithm before declaring it as a solution. Like check the fact that the answer can be ODD so IT ISNT 2^ANYTHING!!!!!!!!!!!!11

{well somebody here needs to check their algorithm before declaring it as a solution. Like check the fact that the answer can be ODD so IT ISNT 2^ANYTHING!!!!!!!!!!!!}

It looks to me that there are two possible interpretations of this:

Q1) Taking 1 or 2 steps, how many ways to reach the nth step?
A) Fibonacci.

Q2) Taking 1 or 2 steps to next floor, how many ways to reach the nth floor?
A) Power of 2. Two ways to reach next floor.

Interpretation 2 does not really make sense in terms of a puzzle (or real life... 1 or 2 steps and you are already up one floor!?), but that is what the original poster seems to have written. Yet another case of bad problem statement.

IMO, the original poster goofed up and intended Q1 all along.

Ppl, Isn't some data missing in this question? Say, the number of steps to climb up one floor perhaps. ie No.of steps/floor. This data is required to answer the question the way it is worded.

I guess the answer might be Summation from b=0 to b=n/2 of (n-b)!/a!b!

The number of steps/floor should not matter. ( assume there are k steps/floor , so total steps now are n*k=m. So instead of n now we have m, butthe problem remains same)

Let's consider this:
We need to climb n steps, using a number of 1 steps and b number of 2 steps.
so
a*1 + b*2=n
a+2b=n

ok,
now given a value of n, above equation can be satisfied by many possible value pairs (a,b).

Let's consider one such pair.
For this particular pair, how many possible ways are there to reach n?
Let's take an example?
if n=5, a=3 and b=1
the question is how many possible ways can I arrange 3 one's and 1 two?
this is typical combination/permutation problem with standard formula answer
(n-b)!/a!b!

so given a value pair a and b, there are (n-b)!/a!b! ways to reach step n.
so the second part is, how many such value pairs are possible? and for each such value pair calculate (n-b)!/a!b!.

not as lengthy as an explaination as I would like. but hth.

I have no idea what the fuss is all about. It is a simple Fibbonacci series.

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

You can reach the nth floor either from n-1 st floor or directly from n-2 nd floor. so total ways to reach nth floor = ways to reach n-1 st floor + ways to reach n-2 nd floor.

unsigned int countPaths(int height,int cur_step)
{
 static int tot=0;
 if(cur_step < height){
   countPaths(height,cur_step+1);
   countPaths(height,cur_step+2);
 }
 else if (cur_step==height){
   ++ tot;
 }
 return tot;
}

It is a simple Fibbonacci series.

f(n) = f(n-1) + f(n-2)+2
where f(x) indicate how many u can go to x th floor..
You can reach the nth floor either from n-1 st floor or directly from n-2 nd floor. so total ways to reach nth floor = ways to reach n-1 st floor + ways to reach n-2 nd floor.

after reaching n-1th floor there is only one way to reach nth floor;after reaching (n-2)th floor there are 2 ways to reach the nth floor...hence total 3 ways

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

please tell me if that is wrong ?

Adhi, it is exactly fibonacci series.

reason is
1. if n = 1, reaching 1st floor is only one way (in one step) so f(1) = 1
2. if n = 2, reaching 2nd floor is two ways (take two steps one a time or take two steps once) so f(2) = 2

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

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

perfectly fibonacci series.

Surprising to see how many people got this question wrong!
It is really simple if you just think about it....

In order to go up one floor (N=1), there are 2 ways (1 step or 2 steps)
in order to go two floors (N=2), There are 4 ways (11,12,21,22 steps)
in order to go three floors (N=3), There are 8 ways (111,121,211,221,112,122,212,222)
so there are 2^N posibilities. If someone starts on the 1st floor, there are 2^8 = 256
possibilities. If someone starts from the basement, there are 2^9 = 512 possibilities.

Can any buddy give me a complete code actually i have to submit assignment of shell on monday so dont want to waste time for this program simple my question has modified fibbonaci instead of 1 ,2 i have 1 , 2 , 3 no of stairs that i can climb together.

I viewed it as generating strings from length n/2 (just "2"s) to n (just "1"s) and came up with that formula (use as query term in wolframalpha.com to display):

sum (n-k) choose k, k=0 to n/2

Explanation: For n=6 stories I can go "222" (l = 3 = n/2), "111111" (l = n = 6), "2211" (l = 4 = n/2 + 1), "2121", "2112", "1212", ..., "21111" (l = 5 = n/2 + 2), ..., "11112".
In each String of length l (which can go from n/2 to n -- 3 to 6 in the example) i can "choose" only (n - l) possitions to take 2 steps at once.
In the example: (3 choose 3) + (4 choose 2) + (5 choose 1) + (6 choose 0) = 13

I read that it is the fibonacci series, but seriously -- how could one come up with this based on that question?!?

Assume each floor has m steps. Each floor can be reached in Fib(m) ways as given in the first answer. For for reaching nth floor as per permutation it should be (Fib(m))^n

int no_of_ways(int n){
    
    if(n == 1) return 1;
    
    if(n == 2) return 2;
    
    return no_of_ways(n-1) + no_of_ways(n-2);
     
 
}