Solution to Codility Lesson: Ladder and steps or rungs

hey, I know you are searching for some programming code relates to ladder and steps or rungs. here, i will explain you about the problem of ladders and steps to reach at top in N number of steps . this question is most common ask or giving for coding or machine test.

Task description

You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:

  • with your first step you can stand on rung 1 or 2,
  • if you are on rung K, you can move to rungs K + 1 or K + 2,
  • finally you have to stand on rung N.

Your task is to count the number of different ways of climbing to the top of the ladder.

For example, given N = 4, you have five different ways of climbing, ascending by:

  • 1, 1, 1 and 1 rung,
  • 1, 1 and 2 rungs,
  • 1, 2 and 1 rung,
  • 2, 1 and 1 rungs, and
  • 2 and 2 rungs.

Given N = 5, you have eight different ways of climbing, ascending by:

  • 1, 1, 1, 1 and 1 rung,
  • 1, 1, 1 and 2 rungs,
  • 1, 1, 2 and 1 rung,
  • 1, 2, 1 and 1 rung,
  • 1, 2 and 2 rungs,
  • 2, 1, 1 and 1 rungs,
  • 2, 1 and 2 rungs, and
  • 2, 2 and 1 rung.

The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.

Write a function:

function solution(A, B);

that, given two non-empty arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].

For example, given L = 5 and: A[0] = 4 B[0] = 3 A[1] = 4 B[1] = 2 A[2] = 5 B[2] = 4 A[3] = 5 B[3] = 3 A[4] = 1 B[4] = 1

the function should return the sequence [5, 1, 8, 0, 1], as explained above.

Write an efficient algorithm for the following assumptions:

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

First Solution for Ladders and steps:

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B) {
    // write your code in JavaScript (Node.js 4.0.0)
    
    var i = 0;
    var result = [];
    var max = 0;
    var steps = [];
    var stepsSum = [];
    var maxB = 0;
    
    steps[0] = 1;
    steps[1] = 1;
    
    for(i=0; i<A.length; i++) {
        max = Math.max(max, A[i]);
        maxB = Math.max(maxB, B[i]);
    }
    
    i = 1;
    while(i++ <= max) {
        steps[i] = (steps[i-1] + steps[i-2]) % Math.pow(2, maxB);
    }
    
    for(i=0; i<A.length; i++) {
        var div = steps[A[i]] & (Math.pow(2, B[i]) - 1);
        result.push(div);
    }
    
    return result;
}

Another solution for ladders and rungs is:

class Solution {
      public int[] solution(int[] a, int[] b) {

        int[] result = new int[a.length];

        int n = getMax(a);
        int p = getMax(b);

        int[] cache = buildCache(n, p);

        for (int i = 0; i<a.length; i++) {
            result[i] = cache[a[i]] % (int) Math.pow(2, b[i]);
        }

        return result;
    }

    private static int getMax(int[] array) {
        int max = array[0];

        for (int i = 0; i<array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        return max;
    }

    public static int[] buildCache(int n, int p) {
        int[] cache = new int[n+1];
        int previous  = 1;
        int current = 1;

        cache[0] = 1;
        cache[1] = 1;

        int index = 3;

        while (index <= n+1){
            int temp = current;
            current = (previous + current)  % (int) Math.pow(2, p);
            previous = temp;

            cache[index-1] = current;

            index++;
        }

        return cache;
    }
}

Leave a Comment

NETFLIX FREE ACCOUNT
OTT movie releases in January 2022 Netflix Top 10 Shows in India 2022