Medium · sequences

Fibonacci Number

Print the Nth Fibonacci number: F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2). The sequence you've met in the playground examples — now the real version, with edge cases and a performance discussion attached.

At a glancePrint F(N) with two rolling variables and N steps — F(0) = 0 and F(1) = 1, while the naive recursion recomputes the same values exponentially many times.

Problem

Input: one integer N (0 ≤ N ≤ 30).

Output: F(N).

Samples:

Input	Output
`0`	`0`
`10`	`55`

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — carry the pair, not the whole sequence

You never need the earlier Fibonacci numbers — only the last two. Keep a = F(i−1) and b = F(i); each step computes t = a + b and slides the window: a = b; b = t;. After N steps, a is F(N).

Hint 2 — the two base cases

With the sliding pair starting at a = 0, b = 1, running the loop zero times leaves a = 0 (the answer for N = 0) and one pass gives a = 1 (the answer for N = 1). The loop handles both base cases for free — like Factorial, the right structure erases the edge cases.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int t = a + b;
        a = b;
        b = t;
    }
    cout << a << endl;
    return 0;
}

The interview follow-up: the recursive version (fib(n) = fib(n−1) + fib(n−2)) is elegant but re-computes the same values exponentially many times — O(2ⁿ) vs this O(N). Fixing that with memoization is your first taste of dynamic programming. Also: F(47) overflows int (see data types), which is why this problem stops at 30.

Deep dive

Why this works

Two variables carry the whole sequence. Keeping an array wastes memory; naive recursion wastes time. The pair-of-previous-values trick is the reusable idea.

The cost

Iterative: O(n) time, O(1) space. Naive recursion: O(2^n) — fib(40) takes about a second, fib(50) takes about a day.

Where it goes wrong

Writing fib(n-1) + fib(n-2) directly is exponential; it is the standard example of why not to.
F(90) exceeds a 64-bit signed integer. Know where your type stops before you print garbage.

Next step

Bit-level thinking next: Binary Representation.

Two things to remember

Two variables carry the whole sequence.
Naive fib recursion is O(2^n) — the classic trap.

🐞 This version fails — open it and try

Runs one iteration too many — off by one term

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a = 0, b = 1;
    for (int i = 0; i <= n; i++) {
        int t = a + b;
        a = b;
        b = t;
    }
    cout << a << endl;
    return 0;
}