Table of Contents
Problem Statement
Fibonacci Number LeetCode Solution – “Fibonacci Number” states that 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).
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.
Approach
Idea:
The main observation is that each F(i) is depending on the sum of F(i-1) and F(i-2). Thus we can take two variables that will store the initial value, then we will iterate till N to get the result.
explanation
- N==0: return 0
- N==1: return 1
- default: return fib(N-1) + fib(N-2)
let’s talk about the second approach:
Considering the sequence of [34,55,89] we can see a pattern that is if we divide any two consecutive terms, the division results in an identical number close to 1.618 called the golden ratio. Indeed we have the formula to do this! called Binet’s formula.
Okay? how can we use this golden something! 34 is the 9th term, If we find the pow(golden,Nth term)/sqrt(5) enclosed with a round function, we would get the Nth term value in O(1) time & space!
Code
C++ Code of Fibonacci Number
class Solution {
public:
int fib(int n) {
if(n==0)
return 0;
if (n==1)
return 1;
int a=0,b=1,c;
for(int i=1;i<n;i++)
{
c=a+b;
a=b;
b=c;
}
return c;
}
};JAVA Program of Fibonacci Number
class Solution {
public int fib(int n) {
if(n==0)
return 0;
if (n==1)
return 1;
int a=0,b=1,c=0;
for(int i=1;i<n;i++)
{
c=a+b;
a=b;
b=c;
}
return c;
}
}Complexity Analysis for Fibonacci Number LeetCode Solution
Time Complexity
O(N)
Space Complexity
O(1)