DSA problem
Nth Fibonacci Number
Given an integer N, return the Nth Fibonacci number, where fib(0) = 0 and fib(1) = 1. This is the single-term counterpart to generating the full series.
The naive recursive definition fib(n) = fib(n-1) + fib(n-2) is elegant but runs in exponential O(2^N) time because it recomputes the same sub-problems repeatedly. The iterative solution instead walks from the bottom up, keeping only the previous two values, and finishes in O(N) time with O(1) space.
This problem is a classic gateway to memoization and dynamic programming, and interviewers often use it to introduce the trade-off between code elegance and performance.
Examples
Example 1
Input:
N = 10Output:
55Explanation: fib(10) = 55, since the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 has 55 at index 10.
Constraints
- 0 <= N <= 40
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.