4 kyu
Big Generalized Fibonacci numbers
83 of 113dolamroth
Description:
Fibonacci sequence is defined as follows: F(n+1) = F(n) + F(n-1)
, where F(0) = 0, F(1) = 1
.
There are many generalizations, including Tribonacci numbers, Padovan numbers, Lucas numbers, etc. Many of there have their respective katas in codewars, including:
- Fibonacci: https://www.codewars.com/kata/fibonacci-number
- Tribonacci: https://www.codewars.com/kata/tribonacci-sequence
- Padovan: https://www.codewars.com/kata/padovan-numbers
- Lucas: https://www.codewars.com/kata/lucas-numbers
And some of the performance versions:
- Millionth Fibonacci kata: https://www.codewars.com/kata/the-millionth-fibonacci-kata
- Big Big Big Padovan Number: https://www.codewars.com/kata/big-big-big-padovan-number
This kata is aimed at evaluating both generalization ability and complexity of the algorithm.
The task:
You are given two lists of integers A
and B
of same size, and a positive integer n
.
- List
A
represents first values of the sequence, namelyF(0) == A(0), F(1) == A(1), ..., F(len(A)-1) = A(len(A)-1)
- List
B
represents coefficients of recurrent equationF(n) = B(0)*F(n-1) + B(1)*F(n-2) + ... + B(len(B)-1)*F(n-len(B))
n
is the index of number in the sequence, which you need to return.
Hint
: solution must have O(log n)
complexity to pass the tests.
Range of numbers:
There are 100
random tests. 2 <= len(A) == len(B) <= 5, 0 <= n <= 100000
. Initial values are in range [-5; 5]
, and the coefficients are in range [-2; 2]
Performance
Algorithms
Mathematics
Big Integers
Similar Kata:
Stats:
Created | Sep 13, 2019 |
Published | Sep 13, 2019 |
Warriors Trained | 1081 |
Total Skips | 250 |
Total Code Submissions | 805 |
Total Times Completed | 113 |
Python Completions | 83 |
Java Completions | 18 |
JavaScript Completions | 22 |
Total Stars | 52 |
% of votes with a positive feedback rating | 96% of 47 |
Total "Very Satisfied" Votes | 45 |
Total "Somewhat Satisfied" Votes | 0 |
Total "Not Satisfied" Votes | 2 |
Total Rank Assessments | 8 |
Average Assessed Rank | 5 kyu |
Highest Assessed Rank | 4 kyu |
Lowest Assessed Rank | 6 kyu |