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 F(n).
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
0 <= n <= 30
Solutions (Click to expand)
The ith fibonacci number is the sum of the i-1th and i-2th number. We can solve this without using recursion by calculating the 1...n fibonacci numbers in order. This way we can calculate the ith number of the fibonacci sequence by taking the result of calculating the i-1th number and the i-2th number.
If we know that the first two numbers are 0 and 1, then we can solve the 3rd number by taking the sum of 0 and 1. For the 4th, we need to find the some of the 2nd and 3rd number. The 2nd we already know to be 1 and the 3rd number is the number we calculated earlier. For the 5th number we need to find the sum of the results of calculating the 3rd number and the 4th.
This would go on until we reach the nth which we can solve by summing the result of calculating the n-1th and n-2th numbers.
We'll keep track of 2 variables, first will be the i-2th fib. number and second will be the i-1th fib. number. After calculating a ith fib number, first we'll be reassigned to second and second will be reassigned to the ith fib number. This way when we calculate the i+1th number first will be the i-1th number and second will be the ith number.
This would go on until we calculate the n number.
Time: O(N)
Space: O(1)