Last Updated: 3 Feb, 2022
Tribonacci Sequence
Moderate
Asked in company
You are given an integer ‘N’. Your task is to find out the ‘N’th Tribonacci Number. ‘N’th number in the Tribonacci sequence is defined as Tn = T n - 1 + Tn - 2 + Tn - 3. Where T0 = 0, T1 = 1, T2= 1. Return the answer in mod of 109 + 7.
For Example :
You are given ‘N’ = 5, Here we know 0th, 1st and 2nd Tribonacci numbers are 0, 1 and 1 respectively. Therefore we can calculate the 3rd number as 0 + 1 + 1 = 2 and 4th number as 1 + 1 + 2 = 4 and 5th number as 1 + 2 + 4 = 7. Hence the answer is 7.
Follow Up :
Can you solve it in logarithmic time?
Input Format :
The first input line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains a single integer ‘N’ representing Tribonacci number to find.
Output Format :
For each test case, print a single integer, representing the ‘N’th Tribonacci Number.
Print a separate line for each test case.
Constraints :
1 ≤ T ≤10
0 ≤ N ≤ 10^5
Time Limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
In this approach, we will make the function recursive, since and then add the base cases the Tribonacci sequence that is given in the question.
We will implement it as `F(n) = F(n - 1) + F(n - 2) + F(n - 3)`
Algorithm:
- If ‘N’ is 0 return 0
- If ‘N’ is 1 or 2 return 1
- Otherwise recursively call the function on ‘N’ - 1, ‘N’ - 2 and ‘N’ - 3 and return the sum of all function calls with a mod of 10^9 + 7
In this approach, we will try to create an array of N length, where the ith index will store the ‘i’th index in the array. We can intialise tribonacci[0], tribonacci[1] and tribonacci[2] as 0, 1, 1.
Algorithm:
- Create an array ‘N’ + 1 length called ‘tribonacci’
- Set ‘tribonacci[0]’, ‘tribonacci[1]’ and ‘tribonacci[2]’ as 0, 1 and 1 respectively.
- Iterate ‘pos’ from 3 to ‘N.’
- Set ‘tribonacci[pos]’ as ‘tribonacci[pos - 1]’ + ‘tribonacci[pos - 2]’ + ‘tribonacci[pos - 3]’
- Return ‘tribonacci[N]’ with a mod of 10^9 + 7
In this approach, we will store only the last three values instead of an entire array. We can see from the previous approach that we only require last the three values of the sequence at any given moment.
Algorithm:
- If ‘N’ is 0, return 0
- If ‘N’ is 1 or 2 return 1.
- Set ‘T0’, ‘T1’ and ‘T2’ as 0, 1 and 1, respectively.
- Iterate N - 2 times
- Set ‘Tn’ as ‘T0’+‘T1’ + ‘T2’
- Set ‘T0’ as ‘T1’
- Set ‘T1’ as ‘T2’
- Set ‘T2’ as ‘TN’
- Finally, return TN with a mod of 10^9 + 7
In this approach, if we take the ‘matrix’ [ [0, 1, 0], [0, 0, 1], [1, 1, 1] ] and multiply it by another matrix as [[Tn], [Tn+1], [Tn+2]], we get a matrix
[ [ 0*Tn + 1*Tn + 1 + 0*Tn + 2 ]
[ 0*Tn + 0*Tn + 1 + 1*Tn + 2 ]
[ 1*Tn + 1*Tn + 1 + 1*Tn + 2 ] ]
Which is equal to:
[ [Tn + 1], [Tn + 2], [Tn + Tn + 1 + Tn + 2] ],
Hence we can see that:
(matrix) * (Mn) = Mn + 1
(matrix) * (Mn - 1) = Mn
(matrix) * (Mn - 2) = Mn - 1,
And so on….
Therefore Mn = ( matrix ^ n ) * ( M0 ),
where ‘M0’ is [ [0], [1], [1] ]
And we know the fastest way to find exponent is in logarithmic time.
We will create a pow(matrix, n) function, where ‘matrix’ is the given matrix and ‘n’ is the exponent. We will also create multiplyMatrix(A, B) which returns a matrix which is the result of A*B
Algorithm:
- In the matrixMultiply(A, B):
- Create a ‘res’ matrix with a size equal to rows of ‘A’ X columns of ‘B’
- Iterate over ‘A’ column by column and ‘B’ row by row and store the multiplication in ‘res’. Store each value in ‘res’ with a mod of 10^9 + 7.
- Finally, return ‘res’
- In the pow(matrix, x)
- If ‘x’ is ‘1’, the return ‘matrix’
- Set ‘half’ as pow(matrix, x / 2)
- Set ‘res’ as ‘matrixMultiply(matrix, matrix)’
- If ‘x’ is odd set ‘res’ as ‘matrixMultiply(matrix, matrix)’
- Finally, return ‘res’
- In the main function:
- Set the ‘initailMatrix’ = [[0], [1], [1]]
- Set ‘matrix’ as ‘[[0, 1, 0], [0, 0, 1], [1, 1, 1]]’
- Set ‘finalMatrix’ as ‘matrixMultiply(pow(initialMatrix, N), initialMatrix))’
- Return the first element of the row of ‘finalMatrix’ with a mod of 10^9 + 7.