algoadvance

Leetcode 1137. N

Problem Statement:

The Tribonacci sequence T(n) is defined as follows:

• T(0) = 0, T(1) = 1, T(2) = 1,
• and T(n+3) = T(n) + T(n+1) + T(n+2) for n >= 0.

Given n, return the value of T(n).

Clarifying Questions:

1. Input Range: What is the expected range of n?
   • Usually, n will be a non-negative integer, and typical edge cases include values like 0, 1, 2.
2. Efficiency: Are there any constraints on time or space complexity we should consider?
   • For example, should we optimize for large n values, or is a straightforward approach sufficient?
3. Input Validation: Do we need to validate the input for non-integer values or negative numbers?
   • Generally assumed to be non-negative integers as per the problem statement.

Strategy:

• Since the Tribonacci sequence follows a specific pattern, a dynamic programming approach can be employed.
• We will use an iterative approach to compute the Tribonacci number for given n, storing interim results to avoid recomputation.

Code:

public class Tribonacci {

    public static int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        int a = 0, b = 1, c = 1, d = 0;
        
        for (int i = 3; i <= n; i++) {
            d = a + b + c;  // Compute the next Tribonacci value
            a = b;  // Update values for the next iteration
            b = c;
            c = d;
        }
        
        return d;
    }

    public static void main(String[] args) {
        // Test cases
        int n = 4;
        System.out.println("T(" + n + ") = " + tribonacci(n));  // Output: 4

        n = 25;
        System.out.println("T(" + n + ") = " + tribonacci(n));  // Output: 1389537
    }
}

Time Complexity:

• O(n): The loop runs n-2 times, which is linear in time complexity.
• Space Complexity:
  • O(1): We are using a constant amount of space (variables a, b, c, d).

Each of these variables is updated in each iteration, so we do not need extra space that grows with n.

This approach efficiently computes the N-th Tribonacci number using iteration and simple state update.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?