Skill Subsist Impulse Ltd Interview Question
Software DevelopersCountry: India
Interview Type: In-Person
bogdan.zima is of course correct. A better way to prove is this identity.
suppose the no of ways you can take step n is defined by a function step(n).
Now, clearly, as only 1 or 2 step at a time are allowed, you could have reached step(n)
by :
one step + take rest of (n-1) OR two steps + take rest of (n-2) steps.
Tow independent count of choices, and thus must get added up.
Hence:
step(n) = step(n-1) + step(n-2) // this gives Fibonacci sequence.
You can generalize it.
// ZoomBA
$count = 0
def count_stais( cur,path, max ){
if ( cur > max ) return
if ( cur == max ){
println( path ) ; $count += 1
return
}
count_stais( cur + 1 , path + '->1' , max )
count_stais( cur + 2 , path + '->2' , max )
}
count_stais( 0 , '' , 4 )
println ( $count )
You can look at the recursive code, and decide the same!
Hi this is one of this problems that looks extremaly intimidating but somehow ends up being easy. If you check the number of ways for first few stairs length you can see that ways one can climb a staircase in respect to staircase length grows exacly like fibonacci number sequence. Lets say one step move = 1, and two steps move = 2. Possible ways for:
1 step staircase => 1 = {1} -> 1 way
2 step => 2 = {1+1}, {2} -> 2 ways
3 step => 3 = {1+1+1}, {1+2}, {2+1} -> 3 ways
4 step => 4 = {1+1+1+1}, {1+1+2}, {2+1+1}, {1+2+1}, {2+2} -> 5 ways
5 step => 5 = {1+1+1+1+1}, {2+1+1+1}, {1+2+1+1}, {1+1+2+1}, {1+1+1+2}, {2+2+1},
{1+2+2}, {2+1+2} = 8 ways.
ways(5) = ways(4) + ways(3) = 5 + 3 = 8.
I use sequencial code for optimal space complexity and additional array to store partial results to reduce time complexity to linear.
- bogdan.zima October 07, 2016