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.

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 = 4 B = 3 A = 4 B = 2 A = 5 B = 4 A = 5 B = 3 A = 1 B = 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 = 1;
steps = 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;

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 = 1;
cache = 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;
}
}