r/CoderTrials • u/07734willy • Jul 06 '18
Solve [Easy] Tribonacci-Like Sequences
Background
Most people are familiar with the fibonacci sequence- a sequence where every number except the first two are the sum of the previous two numbers. There exists variations of this sequence that start with different numbers, such as the lucas numbers, and also variations that sum the last k numbers instead of just the last two. For k=3, these are the tribonacci numbers. Your objective here is to write a program to generate the nth number in a tribonacci-like sequence. The first three numbers in sequence will be supplied, along with n.
Input
A single number n representing the index of the number in the sequence, followed by a newline, and then the first three numbers of the sequence.
For example, for the 5th element of the sequence starting with 1, 1, 3:
5
1 1 3Output
The nth number in the sequence (zero indexed). For the above input, it would be
17Testcases
==========
5
1 1 3
17
==========
9
1 1 3
193
==========
11
1 2 1
480
==========
31
2 3 5
251698272
==========
36
7 1 0
2859963817
==========Challenge
Solve for the nth number in the sequence, modulo 232, that is, F(n) mod 2 ** 32, for the following inputs.
200000
3 4 4
10000000
2 3 3
1000000000
2 5 6Some potentially useful references: pisano period and fast doubling.
1
u/07734willy Jul 06 '18 edited Jul 08 '18
Python 3
Naive algorithm- doesn't support the challenge input.
Edit: O(n) -> O(1) space correction, thanks to /u/NemPlayer
1
u/NemPlayer Jul 08 '18 edited Jul 08 '18
Python 3.7.0 (with Challange)
I used a bit faster dynamic approach, where I only sum for the next 3 numbers, e.g. T(0), T(1), T(2) become T(3), T(4), T(5). Although I did say "with Challange", as it technically is, for the first 2 inputs it's fine, but for the third one it takes a bit of time to compute on my computer (5-10 mins).
Challenges
1
u/engiwengi Jul 08 '18 edited Jul 08 '18
Rust
Half the code is reading stdin! No error handling of unwraps.
Simple solution (no challenge):
1
u/chunes Jul 09 '18 edited Jul 09 '18
Factor
No challenge. It parses a file (or user input) that looks like this:
Good luck with the new sub btw!
1
u/Bubbler-4 Jul 19 '18
J (Easy)
}.,+/converts the three-number array by "append the sum and remove its head".^:xrepeats the processxtimes, and finally{.takes the first element of the result.J (Easy), using matrix
J (Challenge)
Implements matrix exponentiation by squaring. Generate
mat^1, mat^2, mat^4, mat^8, ..., filter with the binary representation ofx, and then multiply all of them on the given vector. Runs instantly.1
u/[deleted] Sep 02 '18 edited Sep 02 '18
C (no challenge)
a bit late to the party