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.
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check