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

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

• javascript
• algorithm

• 1 @meowgoesthedog fixed – pihh Commented Jul 30, 2018 at 19:23
• 1 @mplungjan added the console log and mented after – pihh Commented Jul 30, 2018 at 19:23
• The page you linked to states "The number of different ways can be very large, so it is sufficient to return the result modulo 2^P, for a given integer P." and also that P will never be larger than 30. You seem to be ignoring the B array argument from which you should take P. – Bergi Commented Jul 30, 2018 at 19:29
• 1 Anyone can explain why the downvotes? It seems a legit question. – pihh Commented Jul 31, 2018 at 12:35

3 Answers 3

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

Here is a python 100% answer that I hope offers an explanation :-)

In a nutshell; modulus % is similar to 'bitwise and' & for certain numbers. eg any number % 10 is equivalent to the right most digit.

284%10 = 4
1994%10 = 4

FACTS OF LIFE:

1. for multiples of 2 -> X % Y is equivalent to X & ( Y - 1 )
2. preputing (2**i)-1 for i in range(1, 31) is faster than puting everything in B when super large arrays are given as args for this particular lesson.
3. Thus fib(A[i]) & pb[B[i]] will be faster to pute than an X % Y style thingy.

https://app.codility./demo/results/trainingEXWWGY-UUR/

And for pleteness the code is here.

https://github./niall-oc/things/blob/master/codility/ladder.py

Here is my explanation and solution in C++:

Compute the first L fibonacci numbers. Each calculation needs modulo 2^30 because the 50000th fibonacci number cannot be stored even in long double, it is so big. Since INT_MAX is 2^31, the summary of previously modulo'd numbers by 2^30 cannot exceed that. Therefore, we do not need to have bigger store and/or casting.

Go through the arrays executing the lookup and modulos. We can be sure this gives the correct result since modulo 2^30 does not take any information away. E.g. modulo 100 does not take away any information for subsequent modulo 10.

vector<int> solution(vector<int> &A, vector<int> &B)                            
{                                                                               
  const int L = A.size();                                                       
  vector<int> fibonacci_numbers(L, 1);                                          
  fibonacci_numbers[1] = 2;                                                     
  static const int pow_2_30 = pow(2, 30);                                       
  for (int i = 2; i < L; ++i) {                                                 
    fibonacci_numbers[i] = (fibonacci_numbers[i - 1] + fibonacci_numbers[i - 2]) % pow_2_30;
  }                                                                             
                                                                                
  vector<int> consecutive_answers(L, 0);                                        
  for (int i = 0; i < L; ++i) {                                                 
    consecutive_answers[i] = fibonacci_numbers[A[i] - 1] % static_cast<int>(pow(2, B[i]));
  }                                                                             
                                                                                
  return consecutive_answers;                                                   
}