Solution to Fib-Frog by codility

11 Mar

Question: https://codility.com/demo/take-sample-test/fib_frog

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)).

12 thoughts on “Solution to Fib-Frog by codility

    • 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.

  1. Mine sollution:

  2. 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.

    • Thanks and welcome back!!!

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

      PS: I merged your comments 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *