Return the nth Fibonacci number (0-indexed).

Interview question: Fibonacci Number

The Fibonacci numbers form a sequence such that each number is the sum of the two preceding ones, starting from `0` and `1`.

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

Given `n`, return `F(n)`.

- Fibonacci starts with `F(0) = 0` and `F(1) = 1`.
- Every later value is the sum of the two previous values.
- The input `n` asks for the 0-indexed value `F(n)`.

Understand the Sequence

- The formula naturally translates into recursion.
- However, plain recursion recomputes the same values many times.
- That makes it exponential and too slow for larger `n`.

Recursive Definition

- To compute the next Fibonacci number, we only need the previous two.
- Store them as `a` and `b`, representing consecutive Fibonacci values.
- Repeatedly advance the pair until `a` reaches `F(n)`.

Keep Only the Last Two Values

- Start with `a = 0` and `b = 1`.
- Each loop moves from `(F(i), F(i+1))` to `(F(i+1), F(i+2))`.
- After `n` moves, `a` is the desired answer.

Iterate Up to n

- The iterative solution avoids repeated work.
- Time complexity is O(n).
- Space complexity is O(1) because it stores only two integers.