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:

And some of the performance versions:

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, namely F(0) == A(0), F(1) == A(1), ..., F(len(A)-1) = A(len(A)-1)
  • List B represents coefficients of recurrent equation F(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

Stats:

CreatedSep 13, 2019
PublishedSep 13, 2019
Warriors Trained1081
Total Skips250
Total Code Submissions805
Total Times Completed113
Python Completions83
Java Completions18
JavaScript Completions22
Total Stars52
% of votes with a positive feedback rating96% of 47
Total "Very Satisfied" Votes45
Total "Somewhat Satisfied" Votes0
Total "Not Satisfied" Votes2
Total Rank Assessments8
Average Assessed Rank
5 kyu
Highest Assessed Rank
4 kyu
Lowest Assessed Rank
6 kyu
Ad
Contributors
  • dolamroth Avatar
  • uttumuttu Avatar
Ad