Count the number of different ways of climbing to the top of a ladder.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/13-fibonacci_numbers/ladder/
- Time Complexity:
Solution:
Solution to Codility's Ladder problem which is from the Codility Lesson 13: Fibonacci numbers and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to count the number of different ways of climbing to the top of a ladder. You can find the question of this Ladder problem in the Codility website.
package Codility.Lesson13;
import java.util.*;
public class Ladder {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 4, 4, 5, 5, 1 };
int[] a2 = { 3, 2, 4, 3, 1 };
int[] result2 = solution(a1, a2);
System.out.println(Arrays.toString(result2));
}
public static int[] solution(int[] A, int[] B) {
// for a given N rungs, the number of different ways of climbing is the (N+1)th
// element in the Fibonacci numbers.
// we know that the result of a number modulo 2^P is the bit under P, so
// if we first let the number modulo 2^Q(Q > P) and then modulo 2^P, the
// result is the same.
int L = A.length;
int[] fib = new int[L + 2];
int[] result = new int[L];
fib[1] = 1;
fib[2] = 2;
for (int i = 3; i <= L; i++) {
// make sure the fibonacci number will not exceed the max integer in java 1<<n =
// 2^n
fib[i] = (fib[i - 1] + fib[i - 2]) % (1 << 30);
}
for (int i = 0; i < L; i++) {
result[i] = fib[A[i]] % (1 << B[i]);
}
return result;
}
}