N-th Tribonacci Number

About the problem:

Just like the Fibonacci sequence, which can be defined as F_n = F_n-1 + F_n-2 where F[0] = 0, F[1] = 1, the Tribonacci sequence can be defined as T_n = T_n-1 + T_n-2 + T_n-3 where T[0] = 1, T[1] = 1,T[2] = 1. Here we are provided with a number and we are to return T_n.

Example 1:
Input: 15
Output: 3136

Example 2:
Input: 26
Output: 2555757

Approach #1: Recursion, Brute Force

In this approach, we simply make recursion for the last three values for every n.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

int getTrib(int n) {
  if (n == 0)
    return 0;

  if (n == 1 || n == 2)
    return 1;

  return getTrib(n - 1) + getTrib(n - 2) + getTrib(n - 3);
}

int main() {

  int n;
  cin >> n;

  cout << getTrib(n);
}

Time complexity: O(3n), we make three recursion calls for every n resulting in an exponential complexity.

Approach #2: Dynamic Programing

In the previous approach, we made calls for the same n again and again, so now we just store the values of n, as we have already calculated the answer, and simply return the calculated value when called.
We have discussed both top-down and bottom-up approaches here.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5;

int trib[N];

int getTribRecursive(int n) {
  if (n == 0)
    return 0;

  if (n == 1 || n == 2)
    return 1;

  if (trib[n] != -1) return trib[n];

  return trib[n] = getTribRecursive(n - 1) + getTribRecursive(n - 2) + getTribRecursive(n - 3);
}

int getTribIterative(int n) {

  trib[0] = 0;
  trib[1] = trib[2] = 1;

  for (int i = 3; i <= n; i++)
    trib[i] = trib[i - 1] + trib[i - 2] + trib[i - 3];

  return trib[n];
}

int main() {

  int n;
  cin >> n;

  memset(trib, -1, sizeof trib);
  // Recursive DP approach i.e, memorization
  cout << getTribRecursive(n) << endl;

  // Iterative DP approach
  cout << getTribIterative(n) << endl;
}

Time complexity: O(n), both the above solutions have a linear runtime complexity.

Approach #3: Space Efficient

The above approach has an O(n) space complexity for storing the values of subproblems. We can reduce it to O(1) as we only need to store the last three values for calculating the values of next.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

using namespace std;

int getTrib(int n) {
  if (n == 0)
    return 0;

  if (n < 3)
    return 1;

  int x = 0, y = 1, z = 1, ans;

  for (int i = 3; i <= n; i++) {
    ans = x + y + z;
    x = y;
    y = z;
    z = ans;
  }
  return ans;
}

int main() {

  int n;
  cin >> n;

  cout << getTrib(n) << endl;

}

Time complexity: O(n)
Space complexity: O(1), only three variables are used.

Approach #4: Matrix Exponentiation

To solve recurrence relations like Fibonacci or, in this case, Tribonacci, matrix exponentiation can be employed.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

using namespace std;

vector < vector < int >> M = {
  {
    1,
    1,
    1
  },
  {
    1,
    0,
    0
  },
  {
    0,
    1,
    0
  }
};
vector < vector < int >> matrixMul(const vector < vector < int >> & A,
  const vector < vector < int >> & B) {
  int n = A.size(), m = B.size(), o = B[0].size();

  vector < vector < int >> C(m, vector < int > (o, 0));

  for (int i = 0; i < n; ++i)
    for (int k = 0; k < m; ++k)
      for (int j = 0; j < o; ++j)
        C[i][j] = C[i][j] + A[i][k] * B[k][j];

  return C;
}

vector < vector < int >> matrixPow(const vector < vector < int >> & A, int k) {
  if (k == 0) {
    vector < vector < int >> C(A.size(), vector < int > (A.size(), 0));
    for (int i = 0; i < A.size(); ++i) C[i][i] = 1;
    return C;
  }
  if (k == 1) return A;

  vector < vector < int >> C = matrixPow(A, k / 2);
  C = matrixMul(C, C);
  if (k % 2 == 1) return matrixMul(C, A);
  return C;
}

int getTrib(int n) {
  if (n == 0) return 0;
  if (n < 3) return 1;

  int a = 0, b = 1, c = 1;

  vector < vector < int >> C = matrixPow(M, n - 2);

  return matrixMul(C, {
    {
      c
    },
    {
      b
    },
    {
      a
    }
  })[0][0];
}

int main() {

  int n;
  cin >> n;
  cout << getTrib(n) << endl;
}

We have three equations:
f(n) = f(n-1) + f(n-2) + f(n-3)
f(n-1) = f(n-1)
f(n-2) = f(n-2)

By turning them into a matrix relation we get:

| f(n) | | 1 1 1 | | f(n-1) |
| f(n-1) | = | 1 0 0 | * | f(n-2) |
| f(n-2) | | 0 1 0 | | f(n-3) |

Since we can compute a matrix exponent by O(log(n)), simplify the relation into exponents.

| f(n) | | 1 1 1 |^(n-2) | f(2) |
| f(n-1) | = | 1 0 0 | * | f(1) |
| f(n-2) | | 0 1 0 | | f(0) |

The matrix multiplication cost is k^3, k=3. So the total cost is O(k^3log(n)).