static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:Tb6e,

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:

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

Example 2:

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

[{"language":"Java","code":"public static int tribonacci(int n) {\n    if (n == 0) {\n      return 0;\n    } else if (n <= 2) {\n      return 1;\n    } else {\n      return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);\n    }\n  }","lang":"java"}]

Complexity

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

Method 2 - Top Down DP with memoization

Code

[{"language":"Java","code":"// Integer[] memo, as nulls are deduced as empty\npublic static int tribonacci(int n) {\n\treturn tribMemo(n, new Integer[n+1]);\n}\n\n\nprivate static int tribMemo(int n, Integer[] memo) {\n\tif (memo[n] != -1) {\n\t\treturn memo[n]; // Return cached value if available\n\t}\n\n\tif (n == 0) {\n\t\treturn 0;\n\t} else if (n <= 2) {\n\t\treturn 1;\n\t} else {\n\t\tmemo[n] = tribMemo(n - 1, memo) + tribMemo(n - 2, memo) + tribMemo(n - 3, memo);\n\t\treturn memo[n]; // Store and return calculated value\n\t}\n}","lang":"java"}]

Method 3 - Bottom up DP

Code

[{"language":"Java","code":"public static int tribonacci(int n) {\n\tif (n == 0) {\n\t\treturn 0;\n\t} else if (n <= 2) {\n\t\treturn 1;\n\t}\n\n\tint[] dp = new int[n + 1];\n\tdp[0] = 0;\n\tdp[1] = dp[2] = 1;\n\n\t// Fill the table iteratively using the recurrence relation\n\tfor (int i = 3; i <= n; i++) {\n\t\tdp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];\n\t}\n\n\treturn dp[n];\n}","lang":"java"}]

Method 4 - DP - O(1)

Code

[{"language":"Java","code":"public int tribonacci(int n) {\n\tif (n == 0) {\n\t\treturn 0;\n\t}\n\n\tif (n <= 2) {\n\t\treturn 1;\n\t}\n\n\tint first = 0, second = 1, third = 1, result = 0;\n\n\tfor (int i = 3; i <= n; i++) {\n\t\tresult = first + second + third;\n\t\tfirst = second;\n\t\tsecond = third;\n\t\tthird = result;\n\t}\n\n\treturn result;\n}","lang":"java"}]

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wrap items-start justify-between gap-4","children":[["$","h1",null,{"className":"text-4xl font-bold text-gray-900 dar

Related Tags

Continue Practicing