# Solution to Ladder by codility

9 Mar

To solve this question, there are two key points. Firstly, for a given N rungs, the number of different ways of climbing is the (N+1)th element in the Fibonacci numbers. Naturally, we could get the following answer. It works well. BUT the detected time complexity is O(L**2). What!!! How could it be?!

So you need to know the second key to achieve 100/100 solution: how to do modulo computation in an optimized manner.

Yes, the detected time complexity is O(L) now.

UPDATE – 12/27/2014: thanks to @Martin. The old solution cannot pass the new test cases. We need to improve the performance again! In Python, the interger could be as large as the memory can hold. Therefore, we do not need to handle with the overflow issue. But at the same time, the big interger is kind of resource-consuming, for both time and space. To achieve a better performance, we need to avoid the big integers when we are computing the fib numbers. Actually, we do not need the full-bit fib number, because only some tailing bits are used in the final result.

### 36 Replies to “Solution to Ladder by codility”

1. parapax says:

what if A[i]=4 and B[i]=1? Then the way to cal modulo is wrong . But your solution can pass all the test cases. I’m confused about it.
Could you explain to me why whis case would not happen ?
Thanks!

• Sheng says:

Why is the way to calculate modulo wrong? If A[i]=4 and B[i]=1, we need the result as Fibonacci_number(4+1) % (2^1).

• parapax says:

Got it.
I was wrong.

• parapax says:

Thanks!

• Sheng says:

My pleasure to see my code helpful!

2. Karol says:

How to avoid O(L**2) complexity in java? I have no idea…
I know you write your code in Python, but maybe you have idea how to make it in java.
Here is my result:
https://codility.com/demo/results/demo833Q9X-4F7/

• Sheng says:

Do not use modulo operation. Use bit shift and bitwise AND operation instead.
Then you should get 100/100.

• Karol says:

Replacing ArrayList with normal array was enough, thanks a lot! 🙂
And for other, that’s my 100/100 in java:
https://codility.com/demo/results/demoR9XCB6-BQZ/

• Sheng says:

Thanks for sharing your Java solution!

• Karol says:

If you want, I can put all my Java solutions, all 100/100. I’ve done lessons 1-7, 10-11. Just contact with me 🙂

• Sheng says:

Thanks for your willingness to share. I strongly recommend you to share them with GitHub. It is a free and widely used service. You could demo your skills and build your reputation there.

• Pierre-Yves says:

I’m surprised that it was enough. Does it mean that it’s easier to achieve enough performence in Java, compared with Python?

• Sheng says:

I do not think so. I believe, they have two different standards for the Python and Java.

3. Patrik Bóna says:

Thanks! I had no idea that modulo with big numbers is so slow. In Ruby normal modulo was failing just in last performance test. So I’ve checked your blog, modified it and now it passess 100/100 and execution time is less than half then before.
Thanks for this tip!

• Sheng says:

It is great to see my code be helpful! And thanks for sharing your solution!

4. Sergey says:

I am not sure that this solution would work for C++. By problem formulation: the number of steps in ladder can be as much as 30000. So to calculate and keep Fibonacci numbers in array will not be possible as it is done in the example above (line:9-10). It will overflow long-long data type. I guess that the whole buzz about modulo operation. It offered in order to avoid this problem.Fortunately, it can be proved that recurrence Fn=Fn-1+Fn-2 works also under module transformation at any step. That can be used inside the loop to keep Fn manageable. However, since modulo 2^p can be different for any number in array A[i], we have to calculate several times and that increase complexity. We cannot create one static lookup Fibonacci array.
I am not sure about Python, but I have doubts that it can keep array of Fibonacci without overflowing up to 30000 elements? (the unknown to me test case bundle may not check that situation)

• Sheng says:

Awesome analysis! Actually you are right. We should do the modulo operation while computing the Fibonacci numbers in the line #8.
In Python, the range of intergers is unlimited, or say only limited by the memory size. So the Python code could pass the test.

• Ziad Nasser says:

This won’t work as values of A[i] are not ascending. In other words, you need either to store or map all of the used fibonacci numbers that you used, or to calculate them at each iteration.
However, there is a way to optimize your algorithm.
I’ve done it with java.
The idea is to calculate only the needed fibonacci numbers, and map them.
You are calculating fibonacci numbers for all the range (for all the possible values of fibonacci until the LIMIT or the size of A), while in reality, you only need that number of values in the worst cast scenario (that they exist in the input).
in other words: the size of array A, could be 30000. but values could be of the range [1,10]. In your code, to solve the problem, you are calculating fibonacci numbers for 30000.
Now for the C++ version, a dynamic array could be allocated, or a linked list, of a custom class, where long long ( or 2 integers ) can be used (why not?) (in this case, functions for adding should be implemented to cover the overflow) (or covering only the first 8 bits of the integer is sufficient) Notice that B[i] is of the range: [1,30], this means that the problem by definition, and Sheng’s solution needs a representation on no more than 30 bits (less than an integer). It can be easily proven that the upper part of the long long is not needed and we only need to AND the lower part with the B calculation that Sheng suggested.
Another suggestion for C++ is to do binary sum.
something like: (a+b) & 255
I know that there isn’t much difference between O(N) and O(3N) but I think O(N) that I have is still better than O(3N) above.
However, here’s my 100/100 solution in java
https://codility.com/demo/results/demoKQUD46-C5W/

• Sheng says:

First of all, thank you for the awesome discussion.
I did use the cache to store all the value of fib, in fib =  * (limit+2). It stores all the value from fib(0) to the up bound (fib(L+1)). Therefore, I do not need to consider whether A[i] is or is not ascending.
Finally, I did used the bitwise operation in my final solution.

5. Martin says:

Hallo Sheng,
I haven’t solved this problem before, so it might have changed it’s description in the meantime. But your solution no longer works.
https://codility.com/demo/results/demo6YYRQB-BRJ/
The issue is, that you compute your fib sequence up to the len(A) insted of max(A)
Long time no see btw 😉

• Sheng says:

Nice to see you again!
I cannot remember the previous description neither. Thanks for your reminder! And I will update the solution.

• Sheng says:

BTW, in the new solution, both len(A) and max(A) works well. But max(A) is better.

6. Hima says:

Hello, Sorry i might be asking very naive question. But i didn’t understand the logic that one could ascend to Nth rung by Fibonacci(N+1) ways.
I could notice it by examples but i don’t exactly understand the logic.

• Sheng says:

Let the f(x) be the number of different ways to achieve the step x.
To achieve step x, you could
either jump from x – 1 by one rung
or jump from x – 2 by two rungs
Therefore f(x) = f(x – 1) + f(x – 2).

7. Ian says:

I used almost the same method as your first solution except declare an empty list instead of a fixed size list ( i.e. result = [] instead of result =  * len(A) ). It got 100/100 score and the time complexity is O(L).
Probably the huge size of array declaration leads to timeout I guess.

• Sheng says:

Also in Python? IMO, allocation memory in batch, like  * len(A), should be more efficient than dynamically increasing it.

8. Daniel says:

Hi, I hope this is still working….I’m trying to understand what the ladder problem is asking…I don’t understand basically what I have to return..I see the example and according what I think module is it doesn’t make any sense…I guess it is because I wrong about what a module is…but according to the first post, I read this ” If A[i]=4 and B[i]=1, we need the result as Fibonacci_number(4+1) % (2^1)” It’s what I understand that the problem is asking and for me module(%) is for example is a divide 3 by 2 I get 1,5 the module for me is 5….well knowing that the vector example that is returned in the ladder example doesn’t match with this definition….I use C++ and % is module and It’s what I believe you suggested but I must have not understood anything……thanks!!!

• Sheng says:

Yes, you misundertood the module operation. Please refer to Wikipedia: https://en.wikipedia.org/wiki/Modulo_operation

9. micropentium6 says:

I didn’t expect there were these much discussion for this one. Is it all about the reminder of Fibonacci numbers that is sufficient to meet the need of possible 2 to the power of N (N<=30)?
In order to meet O(L) time complexity, each calculation must be finished in O(1), which will require some memorization up front. However, it's not possible to calculate Fibonacci(30000) without the help of some BigInteger implementation. Luckily, Codility only asks the reminder of some 2^N. So, we only need to store the reminder of any Fibonacci using 2^L as the divisor. This will make sure we have all bits necessary to do any modulo of 2^p, given p in vector B.

10. Edward says:

Hi, found the solution in ruby 100/100

• Sheng says:

Thanks!

11. Aseem says:

Would it be better to calculate the Fibonacci numbers using the formula in a lambda?
fib = lambda x: int(( pow((1+sqrt(5))/2,x) – pow((1-sqrt(5))/2,x))/sqrt(5))

• Aseem says:

Strangely, it doesn’t. I am not sure why though.

• Sheng says:

I did not check the reason to fail. However, it does not improve the performance in any way, because we need all the numbers from fib(1) to fib(N).

12. Vajda Akos says:

My C++ 100/100 solution:

13. Luiz doleron says:

My 100% C++ solution