# Solution to Fib-Frog by codility

11 Mar

Question Name: Fib-Frog or FibFrog

To solve this question, we are using the Breadth First Search with pruning. For a game with N intermediate nodes, the count of Fibonacci numbers, to say CF, is proportional to log(N) [Wikipedia]. And with our pruning, for each node, there are CF attempts to jump. So the total number of overall attempts is proportional to N*CF = N*log(N). That is, the worst-case time complexity is O(N*log(N)).

### 21 Replies to “Solution to Fib-Frog by codility”

1. Jian says:

Very nice! I used the same idea and wrote the Java solution that got 100% on Codility. Here it is
https://gist.github.com/jianlica/9579661

• Sheng says:

Thanks for sharing your solution!

2. pajton says:

Nice idea! Isn’t that using O(nlogn) memory in worst case? I used a solution using dynamic programming, computing minimal number of steps required to get to position K. The Fibonacci calculation is a bit ugly though:-). Posted here:
https://gist.github.com/bbekier/9782904

• Sheng says:

I think the memory is O(n). Because each position is marked as “accessed” for one and only one time, the statusQueue is of size O(n).
Actually the number of Fibonacci, less than 100,000 here, is constant. So the time is also O(n), if we pre-compute these Fibonacci numbers.

• Jonathan says:

You could also spare the extra memory for the access and instead just set the corresponding element of A to 0.

3. Damian says:

Mine sollution:

• Sheng says:

Fixed the typo according to your comments. Thanks!!!

• Rong says:

optimize and simplify Damian’s solution:

4. micropentium6 says:

First, congrats to the new looking of your blog! Haven’t been here for couple weeks!
Again, here is my dummy code. Codility is cheating! We are not supposed to enter the world of DP yet! There is one more tutorial to go… 🙂
Ugly C++ solution with top-down DP recursively…

I am not sure why fibonacci sequence up to N is proportional to log(N), can you explain a bit more?
———————————
Here goes a cleaner version. Sorry for the mess in the previous comment…
bottom-up DP.

• Sheng says:

Thanks and welcome back!!!
For the fibonacci sequence, up to N, there are at most log(N) fibonacci numbers, which is a math question.

• micropentium6 says:

Looks much better! Thank you for fixing the indents!
in terms of O(logN), my math is bad. It’s not intuitive to me, for the case of 1e6, both 10 based log and e based ln doesn’t come close to 31…Maybe this is just a bad example…

• Sheng says:

What’s 31 here? Probably it is 2-based.

• micropentium6 says:

There are 31 Fibonacci numbers in range of [0,1000000].

• Sheng says:

Big O, such as O(logN) is used to measure the order of complexity, rather than the exact cost (here the exact number of Fibonacci numbers).

5. Tomo says:

Hi, I’ve got 100% using Java and DP approach. Sorry for not commenting the code.

• Saqib says:

I would really love to get in touch with you regarding this solution. As you say it gets “Perfect Score” when submitted to Codility. I would like to understand how it works and especially why it isn’t necessary to calculate the Fib numbers as every other solution seems to be doing. My email is saqib.malik2@gmail.com.

6. Bianca Röper says:

my PHP-version with 100%

7. Daniel says:

Hmm seems like this solution no longer works and only achieves a 58% on codility due to timeouts. However, it did help me visualize how to solve the problem, so thank you for that!

Update: Disregard! Had a typo in my version of it. Still achieves 100%

• Sheng says:

To Err Is Human 🙂

8. Charles says:

My solution, very clean, well explained, and scores 100% on Codility.

9. Luiz doleron says:

This is my 100% soluction in C++:
https://app.codility.com/demo/results/trainingX4MTMT-MCS/

The code is pretty similar to yours. BFS but I used a queue