Start learning free

LESSON 166 OF 348 · LOOPS - CHALLENGES

Fibonacci Number in Kotlin: O(n) Time and O(1) Space

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
    Ctrl + Enter to check

    KOTLIN · LOOPS - CHALLENGES

    Fibonacci in Kotlin, explained

    Problem overview

    The function fibonacci(n: Int) returns the n-th Fibonacci number. The sequence starts with F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n - 1) + F(n - 2). The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21.

    For n = 4 the answer is 3, since F(4) = F(3) + F(2) = 2 + 1. The statement asks for O(n) time and O(1) space.

    Approach

    The definition suggests a recursive function that calls itself for n - 1 and n - 2. That works, but it recomputes the same values again and again, and the number of calls grows exponentially. The sequence can be computed by building it from the bottom instead.

    To get the next number you only need the previous two, so there is no reason to remember the rest. Keep two variables, prev and curr, holding F(i - 2) and F(i - 1). On each pass, compute F(i) as their sum and slide both variables one step forward. After the last pass, curr holds F(n). That is one loop and two variables.

    Step by step

    1. Handle the base cases. If n < 2, return n. This works for both: F(0) = 0 and F(1) = 1, so the answer equals the input.
    2. Set up the window. var prev = 0 and var curr = 1 hold F(0) and F(1). They are var because they change on every pass.
    3. Loop from 2 to n. for (i in 2..n) runs once for each of F(2) to F(n). The .. range includes n.
    4. Compute the new number. val next = curr + prev is F(i). It is a val because it is created fresh on every pass and never changed.
    5. Slide the window. Assign prev = curr first, then curr = next. The order protects the old curr: if curr were overwritten first, its value would be lost before prev could take it.
    6. Return curr. After the final pass it holds F(n).

    Tracing n = 4: start with prev = 0, curr = 1. At i = 2, next = 1, so prev = 1 and curr = 1. At i = 3, next = 2, so prev = 1 and curr = 2. At i = 4, next = 3, so prev = 2 and curr = 3. The function returns 3.

    Why the loop is correct

    A useful way to check a loop is to state what is true at the start of every pass. Here, at the start of the pass for i, prev holds F(i - 2) and curr holds F(i - 1). Before the first pass (i = 2) that is true, because prev = F(0) and curr = F(1). The pass computes F(i) and moves the window so the same statement holds for i + 1. When the loop ends after i = n, curr holds F(n). If a change you make breaks this statement, the answer will be wrong.

    The solution in Kotlin

    class Solution {
    fun fibonacci(n: Int): Int {
        if (n < 2) {
            return n
        }
        var prev = 0
        var curr = 1
        for (i in 2..n) {
            val next = curr + prev
            prev = curr
            curr = next
        }
        return curr
    }
}

    Kotlin details:

    • Inclusive range. 2..n contains both 2 and n. When n is 2 it runs once. Because the base case already returned for n < 2, the range is never empty here.
    • val inside a loop. A new next is created in each pass, so it can be read-only.
    • Int overflow. An Int holds values up to 2147483647 and wraps silently past that. fibonacci(46) returns 1836311903, the largest Fibonacci number that fits. fibonacci(47) returns -1323752223, which is wrong. For larger n, declare prev and curr as Long, which holds values up to F(92) (7540113804746346429); with Long variables, F(47) comes out as 2971215073.
    • Not a swap. Kotlin has no tuple assignment like prev, curr = curr, prev + curr, so the three-step update with next is the straightforward way. The values come out the same.

    The window idea is also what makes the space constant. Older numbers such as F(i - 3) are never needed again, so the variables simply move past them and the program forgets them.

    Complexity

    Time: O(n). The loop runs n - 1 times and does a constant amount of work each time.

    Space: O(1). Only prev, curr, next and the loop counter exist, regardless of n. A recursive version would use O(n) stack space, and a version that stores every number in a list would use O(n) memory.

    Why not plain recursion

    The recursive version follows the definition directly:

    fun fibRec(n: Int): Int = if (n < 2) n else fibRec(n - 1) + fibRec(n - 2)

    It returns the right values, but each call starts two more, and the same arguments are computed many times. Counting the calls shows the cost: fibRec(10) makes 177 calls, fibRec(20) makes 21,891 and fibRec(30) makes 2,692,537. The count grows by a factor of about 1.6 for each increase of 1 in n, which is exponential. The loop computes each number once, so for n = 30 it does 29 passes instead of millions of calls.

    Edge cases and common mistakes

    • n = 0 and n = 1. Without the base case the loop 2..n is empty, and the function would return curr, which is 1. That's right for n = 1 but wrong for n = 0, whose answer is 0.
    • Updating in the wrong order. Writing curr = next before prev = curr makes both variables equal next, so the sequence goes wrong from that step on.
    • Returning prev. After the final pass, F(n) is in curr; prev holds F(n - 1).
    • Starting the loop at 3 or stopping at n - 1. Either one performs one pass too few and returns F(n - 1).
    • Overflow. Past n = 46, an Int result is wrong because of wrap-around.

    Testing

    • n = 0 gives 0 and n = 1 gives 1.
    • n = 2 gives 1.
    • n = 3 gives 2.
    • n = 4 gives 3.
    • n = 10 gives 55.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free