Codility Ladder javascript – not understanding a detail that jumps the answer from 37 to 100%

I’m trying to solve all the lessons on codility but I failed to do so on the following problem: Ladder by codility

I’ve searched all over the internet and I’m not finding a answer that satisfies me because no one answers why the max variable impacts so much the result.

So, before posting the code, I’ll explain the thinking.

By looking at it I didn’t need much time to understand that the total number of combinations it’s a Fibonacci number, and removing the 0 from the Fibonacci array, I’d find the answer really fast.

Now, afterwards, they told that we should return the number of combinations modulus 2^B[i].

So far so good, and I decided to submit it without the var max, then I got a score of 37%.. I searched all over the internet and the 100% result was similar to mine but they added that max = Math.pow(2,30).

Can anyone explain to me how and why that max influences so much the score?

My Code:

// Powers 2 to num
function pow(num){
    return Math.pow(2,num);
}
// Returns a array with all fibonacci numbers except for 0
function fibArray(num){
    // const max = pow(30); -> Adding this max to the fibonaccy array makes the answer be 100% 
    const arr = [0,1,1];
    let current = 2;

    while(current<=num){
        current++;
        // next = arr[current-1]+arr[current-2] % max; 
        next = arr[current-1]+arr[current-2]; // Without this max it's 30 %
        arr.push(next);
    }

    arr.shift(); // remove 0
    return arr;

}

function solution(A, B) {
    let f = fibArray(A.length  + 1);
    let res = new Array(A.length);

    for (let i = 0; i < A.length; ++i) {
        res[i] = f[A[i]] % (pow(B[i]));
    }

    return res;
}

console.log(solution([4,4,5,5,1],[3,2,4,3,1])); //5,1,8,0,1 

// Note that the console.log wont differ in this solution having max set or not.
// Running the exercise on Codility shows the full log with all details 
// of where it passed and where it failed.

Answer

The limits for input parameters are:

Assume that:

• L is an integer within the range [1..50,000];
• each element of array A is an integer within the range [1..L];
• each element of array B is an integer within the range [1..30].

So the array f in fibArray can be 50,001 long.

Fibonacci numbers grow exponentially; according to this page, the 50,000th Fib number has over 10,000 digits.

Javascript does not have built-in support for arbitrary precision integers, and even doubles only offer ~14 s.f. of precision. So with your modified code, you will get “garbage” values for any significant value of L. This is why you only got 30%.

But why is max necessary? Modulo math tells us that:

(a + b) % c = ([a % c] + [b % c]) % c

So by applying % max to the iterative calculation step arr[current-1] + arr[current-2], every element in fibArray becomes its corresponding Fib number mod max, without any variable exceeding the value of max (or built-in integer types) at any time:

fibArray[2] = (fibArray[1] + fibArray[0]) % max = (F1 + F0) % max = F2 % max
fibArray[3] = (F2 % max + F1) % max             = (F2 + F1) % max = F3 % max
fibArray[4] = (F3 % max + F2 % max)             = (F3 + F2) % max = F4 % max
and so on ...
(Fn is the n-th Fib number)

Note that as B[i] will never exceed 30, pow(2, B[i]) <= max; therefore, since max is always divisible by pow(2, B[i]), applying % max does not affect the final result.