Grokking 75: Top Coding Interview Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: N-th Tribonacci Number
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

The Tribonacci sequence T<sub>n</sub> is defined as follows:

T<sub>0</sub> = 0, T<sub>1</sub> = 1, T<sub>2</sub> = 1, and T<sub>n + 3</sub> = T<sub>n</sub> + T<sub>n+1</sub> + T<sub>n+2</sub> for n >= 0.

Given an integer n, return the n<sup>th</sup> Tribonacci term T<sub>n</sub>.

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<sup>31</sup> - 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

Python3
Python3
. . . .

Complexity Analysis

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

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible