N-th Tribonacci Number Problem

Problem

The Tribonacci sequence $T_n$ is defined as follows: 

$$ T_0 = 0, T_1 = 1, T_2 = 1, \text{ and }T_{n+3} = T_n + T_{n+1} + T_{n+2} \text{ for n} >= 0. $$

Given n, return the value of $T_n$.

Examples

Example 1:

1
2
3
4
5
6
7

Input:
n = 4
Output:
 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

1
2
3
4

Input:
n = 25
Output:
 1389537

Solution

This problem is very similar to Generate Nth Fibonacci Number. Please refer to that for understanding the problem.

Method 1 - Recursion

Code

1
2
3
4
5
6
7
8
9

  public static int tribonacci(int n) {
    if (n == 0) {
      return 0;
    } else if (n <= 2) {
      return 1;
    } else {
      return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
  }

Complexity

  • Time: O(3^n) - As we branch out in 3 directions
  • Space: O(1)

Method 2 - Top Down DP with memoization

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// Integer[] memo, as nulls are deduced as empty
public static int tribonacci(int n) {
	return tribMemo(n, new Integer[n+1]);
}


private static int tribMemo(int n, Integer[] memo) {
	if (memo[n] != -1) {
		return memo[n]; // Return cached value if available
	}

	if (n == 0) {
		return 0;
	} else if (n <= 2) {
		return 1;
	} else {
		memo[n] = tribMemo(n - 1, memo) + tribMemo(n - 2, memo) + tribMemo(n - 3, memo);
		return memo[n]; // Store and return calculated value
	}
}

Method 3 - Bottom up DP

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public static int tribonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n <= 2) {
		return 1;
	}

	int[] dp = new int[n + 1];
	dp[0] = 0;
	dp[1] = dp[2] = 1;

	// Fill the table iteratively using the recurrence relation
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}

	return dp[n];
}

Method 4 - DP - O(1)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int tribonacci(int n) {
	if (n == 0) {
		return 0;
	}

	if (n <= 2) {
		return 1;
	}

	int first = 0, second = 1, third = 1, result = 0;

	for (int i = 3; i <= n; i++) {
		result = first + second + third;
		first = second;
		second = third;
		third = result;
	}

	return result;
}