Start learning free

LESSON 165 OF 347 · LOOPS - CHALLENGES

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

Practice Read the full explanation

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

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

Given n, calculate and return F(n).

Example 1:

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

Example 2:

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

Example 3:

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

Note:

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

Hints:

As we compute each new Fibonacci number as the sum of the previous two, we will use 2 variables prev and curr to store the last two computed Fibonacci numbers at each moment of time. We should initialize prev with 0(F(0)) and curr with 1(F(1)).

There are n - 1 more numbers to be computed: F(2), F(3), ..., F(n). Let's write a for loop that iterates with a variable i through the values 2 to n. Inside this loop, we shoud compute the new Fibonacci number (F(i)) and update the variables prev and curr.

At the beginning of each iteration, F(i - 2) is stored in prev, F(i - 1) is stored in curr and we want to compute F(i). At the end of the iteration, we want prev to store F(i - 1) and curr to store F(i).
So we can use another variable next to store prev + curr and then we can assign curr to prev (prev = curr) and next to curr (curr = next).

After the loop finishes execution, the answer (F(n)) lies in curr.
Also, don't forget to treat the special cases n = 1 and n = 2 at the beginning of the algorithm.

STEP 1 OF 6

Guided

Ctrl + Enter to check

C# · LOOPS - CHALLENGES

Fibonacci in C#, explained

Problem overview

Fibonacci(int n) returns F(n), where F(0) = 0, F(1) = 1, and every later number is the sum of the two before it. The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

The examples from the statement: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 and F(4) = 2 + 1 = 3.

Approach

The definition suggests a recursive method that calls itself for n - 1 and n - 2. It is correct but slow: it recomputes the same values over and over, and its running time grows exponentially. The statement asks for O(n) time and O(1) space, which points to a loop.

To compute F(i) you only need F(i - 1) and F(i - 2). Nothing older matters, so the loop keeps just those two values and slides them forward one position per iteration. Two variables are enough, whatever n is.

Why the recursive version is slow

The direct translation of the definition looks like this:

static int Fib(int n) {
    if (n < 2) {
        return n;
    }
    return Fib(n - 1) + Fib(n - 2);
}

It is short and correct, but Fib(5) calls Fib(3) twice, Fib(2) three times, and so on. Counting the calls in a test run gave 15 for n = 5, 177 for n = 10, 21,891 for n = 20 and 2,692,537 for n = 30. Each extra step multiplies the work by about 1.6. The loop computes every value exactly once instead.

Step by step

Handle the base cases. F(0) = 0 and F(1) = 1, so for n < 2 the answer is n itself. One if returns it.
Set up the window. prev holds F(0) = 0 and curr holds F(1) = 1. At the start of each pass, prev is F(i - 2) and curr is F(i - 1).
Loop from 2 to n inclusive. That computes F(2) up to F(n), one value per pass.
Compute the new value. next = curr + prev is F(i).
Slide the window. Copy curr into prev first, then next into curr. The order protects the old curr: if you overwrote curr first, the old value would be gone before prev could take it.
Return curr. After the last pass it holds F(n).

Tracing n = 5

`i`	`next`	`prev` after	`curr` after
start		0	1
2	1	1	1
3	2	1	2
4	3	2	3
5	5	3	5

After i = 5, curr is 5, which is F(5).

It helps to see why the loop invariant holds. Before the first pass, prev and curr are F(0) and F(1), so they are the two values for i = 2. After each pass they become F(i - 1) and F(i), which are exactly the two values the next pass needs. Because the statement stays true before every pass, it is still true when the loop ends, and curr is F(n).

The solution in C#

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

Some C# details:

Several variables in one declaration. int prev = 0, curr = 1; declares two int variables, each with its own initial value.
next is declared inside the loop. It exists only for one pass and is created fresh on the next one. next is not a reserved word in C#, so it is a legal name.
The result is an int. That limits how far the sequence can go, as the next section explains.

Complexity

Time: O(n). The loop runs n - 1 times, and each pass does one addition and two assignments.

Space: O(1). The variables prev, curr, next and i are all the memory used, and their number doesn't depend on n.

Edge cases and common mistakes

n = 0 and n = 1. The early return gives 0 and 1. Without it, the loop wouldn't run for these values, and the function would return curr, which is 1, wrong for n = 0.
n = 2. The loop runs once and returns 1. It needs no special case.
Integer overflow. C# int arithmetic wraps around silently by default. F(46) is 1836311903 and fits, but F(47) is 2971215073, which is too large. In a test run, Fibonacci(47) returned -1323752223. A long would reach F(92). For the sizes the lesson's tests use, int is enough.
Wrong assignment order. Writing curr = next; prev = curr; sets both variables to the new value, and the sequence stops growing correctly. Check by hand with prev = 1 and curr = 2: after the update you should have prev = 2 and curr = 3.
Loop bound i < n. This stops one value early and returns F(n - 1).
Negative n. The sequence isn't defined for it, and this solution returns n unchanged because of the n < 2 test. The task's inputs are not negative.

Making overflow visible

Silent wrap-around can hide a wrong answer. If you would rather get an error than a negative number, wrap the addition in the checked operator: int next = checked(curr + prev);. With that change, Fibonacci(46) still returns 1836311903, while Fibonacci(47) throws an OverflowException in a test run. The lesson's solution doesn't need it, but it is a handy habit when a sum might not fit.

Variations worth knowing

The same two-variable loop is the basis of many sequence problems. If the values must go beyond F(46), change the variable types to long, and also the return type if the method should return the full value. With long, the loop gives correct answers up to F(92), whose value, 7540113804746346429, still fits. F(93) does not fit in a long either. Beyond that you need System.Numerics.BigInteger, which can hold any size at a higher cost per addition.

Testing

n = 0 gives 0 and n = 1 gives 1.
n = 2 gives 1, n = 3 gives 2 and n = 4 gives 3.
n = 10 gives 55.

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