easy N-th Tribonacci Number

Problem Statement

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_{n + 3} = T_n + T_n+1 + T_n+2 for n >= 0.

Given an integer n, return the n^th Tribonacci term T_n.

Examples

Example 1

• Input: n = 5
• Expected Output: 7
• Justification: The sequence up to the 5th term is [0, 1, 1, 2, 4, 7]. The 5th term is 7.

Example 2

• Input: n = 8
• Expected Output: 44
• Justification: The sequence up to the 8th term is [0, 1, 1, 2, 4, 7, 13, 24, 44]. The 8th term is 44.

Example 3

• Input: n = 10
• Expected Output: 149
• Justification: The sequence up to the 10th term is [0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149]. The 10th term is 149.

Constraints:

• 0 <= n <= 37
• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2³¹ - 1.

Solution

To solve this problem, we use an iterative approach with three variables to track the last three values in the Tribonacci sequence. This approach reduces space complexity compared to using an array to store all values.

We initialize the first three values as 0, 1, and 1. For each subsequent term up to n, we calculate the next value as the sum of the previous three, then shift the variables to the right. This method is efficient in both time and space, making it suitable for large values of n.

Step-by-Step Algorithm

1. Check if n is less than 3:

   • If n = 0, return 0.
   • If n = 1 or n = 2, return 1.

2. Initialize three variables:

   • a = 0 (represents T0)
   • b = 1 (represents T1)
   • c = 1 (represents T2)

3. Iterate from 3 to n:

   • Calculate the next Tribonacci number as tmp = a + b + c.
   • Update the variables:
     • a = b
     • b = c
     • c = tmp

4. Return c as the n-th Tribonacci number.

Algorithm Walkthrough

For n = 8:

1. Initialization:

   • a = 0
   • b = 1
   • c = 1

2. Iteration steps:

   • Step 1: tmp = a + b + c = 0 + 1 + 1 = 2
     • Update: a = b = 1, b = c = 1, c = tmp = 2
   • Step 2: tmp = a + b + c = 1 + 1 + 2 = 4
     • Update: a = b = 1, b = c = 2, c = tmp = 4
   • Step 3: tmp = a + b + c = 1 + 2 + 4 = 7
     • Update: a = b = 2, b = c = 4, c = tmp = 7
   • Step 4: tmp = a + b + c = 2 + 4 + 7 = 13
     • Update: a = b = 4, b = c = 7, c = tmp = 13
   • Step 5: tmp = a + b + c = 4 + 7 + 13 = 24
     • Update: a = b = 7, b = c = 13, c = tmp = 24
   • Step 6: tmp = a + b + c = 7 + 13 + 24 = 44
     • Update: a = b = 13, b = c = 24, c = tmp = 44

3. Result: The 8th Tribonacci number is 44.

Code

class Solution {

  public int tribonacci(int n) {
    // Handle base cases
    if (n < 3) {
      return n > 0 ? 1 : 0;
    }

    // Initialize the first three Tribonacci numbers
    int a = 0, b = 1, c = 1;

    // Compute Tribonacci numbers iteratively
    for (int i = 0; i < n - 2; ++i) {
      int tmp = a + b + c; // Calculate the next Tribonacci number
      a = b; // Shift the variables
      b = c;
      c = tmp;
    }

    return c; // Return the n-th Tribonacci number
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.tribonacci(5)); // 7
    System.out.println(sol.tribonacci(8)); // 44
    System.out.println(sol.tribonacci(10)); // 149
  }
}

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is since we iterate through the sequence up to n, performing constant-time operations at each step.
• Space Complexity: The space complexity is since we only use a fixed amount of extra space to store the variables a, b, and c.