Start learning free

LESSON 166 OF 347 · LOOPS - CHALLENGES

Tribonacci in C#: O(n) Time and O(1) Space with a for Loop

Practice Read the full explanation

The Tribonacci numbers, commonly denoted T(n) form a sequence, called the Tribonacci sequence, such that each number is the sum of the three preceding ones, starting from 0, 1 and 1. That is,

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

Given n, calculate and return T(n).


Example 1:

Input: n = 3
Output: 2
Explanation: T(3) = T(2) + T(1) + T(0) = 1 + 1 + 0 = 2.

Example 2:

Input: n = 4
Output: 4
Explanation: T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4.

Example 3:

Input: n = 5
Output: 7
Explanation: T(5) = T(4) + T(3) + T(2) = 4 + 2 + 1 = 7.

Note:

Your algorithm should run in O(n) time and use O(1) space.


STEP 1 OF 8
    Ctrl + Enter to check

    C# · LOOPS - CHALLENGES

    Tribonacci in C#, explained

    Problem overview

    Tribonacci(int n) returns T(n). The sequence starts with T(0) = 0, T(1) = 1 and T(2) = 1, and every later number is the sum of the three before it. It begins 0, 1, 1, 2, 4, 7, 13, 24, 44.

    The statement's examples: T(3) = 1 + 1 + 0 = 2, T(4) = 2 + 1 + 1 = 4 and T(5) = 4 + 2 + 1 = 7.

    Approach

    This is the Fibonacci idea with one more term. A recursive method that calls itself three times per level repeats a huge amount of work. The statement asks for O(n) time and O(1) space, so use a loop.

    Each value needs only the three before it. The loop keeps those three in variables: curr is the newest, prev is one step behind it and prev2 is two steps behind. Each pass computes the next number from the three and shifts the window forward by one position.

    Why the recursive version is slow

    The definition translates directly into a method that calls itself three times:

    static int Trib(int n) {
    if (n < 2) {
        return n;
    }
    if (n == 2) {
        return 1;
    }
    return Trib(n - 1) + Trib(n - 2) + Trib(n - 3);
}

    It is correct, but it recomputes the same values many times. Counting the calls in a test run gave 13 for n = 5, 289 for n = 10 and 128,287 for n = 20. The loop below computes each value once, so for n = 20 it makes 18 passes.

    Step by step

    1. Return early for 0 and 1. T(0) = 0 and T(1) = 1 equal n, so if (n < 2) return n; covers both.
    2. Set up the three values. prev2 = 0, prev = 1 and curr = 1 are T(0), T(1) and T(2). Starting the window at T(2) means n = 2 needs no loop at all: curr already holds the answer.
    3. Loop from 3 to n inclusive. Each pass computes one of T(3) through T(n). The <= makes sure n itself is included.
    4. Add the three values. next = prev2 + prev + curr.
    5. Shift the window, oldest first. prev2 = prev, then prev = curr, then curr = next. Each variable is overwritten only after its old value has been copied one place back.
    6. Return curr. It holds T(n).

    Tracing n = 5

    inextprev2prevcurr
    start011
    32112
    44124
    57247

    The function returns curr, which is 7.

    The reasoning behind the loop is the same as for Fibonacci. Before a pass with index i, the three variables hold T(i - 3), T(i - 2) and T(i - 1). The pass adds them to get T(i) and shifts, so the next pass starts with the right three values again. When the loop ends, curr is T(n).

    The solution in C#

    class Solution {
    public int Tribonacci(int n) {
        if (n < 2) {
            return n;
        }
        int prev2 = 0, prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) {
            int next = prev2 + prev + curr;
            prev2 = prev;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

    Some C# details:

    • Three variables, one declaration. int prev2 = 0, prev = 1, curr = 1; declares three int variables, each with its own initial value.
    • The shifts are three separate assignments. C# has no need for a temporary beyond next, because each assignment copies a value that hasn't been overwritten yet.
    • The loop variable is scoped to the loop. i and next exist only inside the for, so they can't clash with other names in the method.

    Complexity

    Time: O(n). The loop runs n - 2 times for n >= 2, with a constant amount of work per pass.

    Space: O(1). Five variables, whatever the value of n.

    Edge cases and common mistakes

    • n = 2. The loop starts at 3, so it never runs, and the function returns curr, which is 1. That is why the window starts at T(2).
    • Treating 2 as a base case that returns n. T(2) is 1, not 2. The shortcut return n works only for 0 and 1.
    • Shifting in the wrong order. Doing curr = next first, then prev = curr, copies the new value into prev and loses the old one. Always move the oldest value first.
    • Integer overflow. C# int arithmetic wraps silently by default. T(37) is 2082876103 and fits, but T(38) is 3831006429, which doesn't. A test run of Tribonacci(38) returned -463960867. A long would last much longer.
    • Loop bound i < n. It stops one number early, so the function returns T(n - 1).

    Making overflow visible

    If you want a loud failure instead of a silent wrong number, compute the sum with the checked operator: int next = checked(prev2 + prev + curr);. A value that no longer fits in an int then throws an OverflowException. The lesson's solution doesn't need it for the sizes it tests.

    Why three variables and not an array

    You could store every value in an array or a List<int> and read the three previous entries by index. That works and is easy to follow, but it needs O(n) space for values you never look at again. Since only the last three matter, three variables do the same job in O(1) space, which is what the statement asks for. The cost is that the shifting has to be done carefully, which is why the order of the three assignments is part of the lesson.

    Relation to Fibonacci

    The only differences from the Fibonacci loop are the extra variable and the extra assignment. The window now has three values instead of two, and each pass shifts all three. The same pattern extends to any "sum of the previous k values" sequence: keep k variables, or an array of size k, and shift them every pass.

    Testing

    • n = 0 gives 0, n = 1 gives 1 and n = 2 gives 1.
    • n = 3 gives 2, n = 4 gives 4 and n = 5 gives 7.
    • n = 8 gives 44.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free