Problem Statement
Calculate the N-th Fibonacci number using an iterative approach. The Fibonacci sequence is defined as:
[ F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) , ext{for} , n > 1. ]
Example
-
Input: n = 5
Output: 5
Explanation: The Fibonacci sequence is 0, 1, 1, 2, 3, 5, ....
-
Input: n = 10
Output: 55
Explanation: The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....
Brute Force Approach
Approach
Idea: Use an iterative approach to calculate the Fibonacci sequence up to the N-th number. Use an array to store all Fibonacci numbers.
Steps
- Handle the base cases for
n = 0 and n = 1. Return 0 and 1, respectively.
- Initialize an array to store the Fibonacci sequence.
- Populate the array by iterating from
2 to n, calculating each Fibonacci number as the sum of the previous two numbers.
- Return the N-th Fibonacci number from the array.
Time & Space Complexity
- Time Complexity: O(n)
- The loop runs
n iterations to calculate the Fibonacci sequence.
- Space Complexity: O(n)
- An array of size
n is used to store Fibonacci numbers.
Code Snippet
Dry Run
Input: n = 5
- Initialize
fib = [0, 1].
- Loop through to populate
fib:
fib[2] = fib[1] + fib[0] = 1 + 0 = 1.fib[3] = fib[2] + fib[1] = 1 + 1 = 2.fib[4] = fib[3] + fib[2] = 2 + 1 = 3.fib[5] = fib[4] + fib[3] = 3 + 2 = 5.
- Return
fib[5] = 5.
Efficient Approach
Approach
Idea: Instead of storing all Fibonacci numbers, maintain only the last two numbers of the sequence to reduce space usage.
Steps
- Handle the base cases for
n = 0 and n = 1. Return 0 and 1, respectively.
- Initialize two variables,
prev1 and prev2, to store the last two Fibonacci numbers.
- Iterate from
2 to n, updating the variables to calculate the next Fibonacci number.
- Return the final value of
prev1, which will hold the N-th Fibonacci number.
Time & Space Complexity
- Time Complexity: O(n)
- The loop runs
n iterations to calculate the Fibonacci sequence.
- Space Complexity: O(1)
- Only two variables are used, regardless of
n.
Code Snippet
Dry Run
Input: n = 5
- Initialize
prev2 = 0, prev1 = 1.
- Loop through:
i = 2: current = prev1 + prev2 = 1 + 0 = 1, update prev2 = 1, prev1 = 1.i = 3: current = prev1 + prev2 = 1 + 1 = 2, update prev2 = 1, prev1 = 2.i = 4: current = prev1 + prev2 = 2 + 1 = 3, update prev2 = 2, prev1 = 3.i = 5: current = prev1 + prev2 = 3 + 2 = 5, update prev2 = 3, prev1 = 5.
- Return
prev1 = 5.
Complexity Analysis
| Operation | Brute Force | Efficient Approach |
|---|
| Time Complexity | O(n) | O(n) |
| Space Complexity | O(n) | O(1) |
Conclusion
- The brute force approach calculates the Fibonacci sequence efficiently but requires additional space for storing all Fibonacci numbers.
- The efficient approach reduces space usage to O(1) by maintaining only the last two numbers of the sequence.
- This problem highlights the importance of space optimization in iterative algorithms.