The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
The Sequence Fn of Fibonacci numbers is defined by the recurrence relation:-
with seed values
Problem Statement:- Given a positive integer n, find the nth fibonacci number. Since the answer can be very large, return the answer modulo 1000000007.
we can solve this problem by both approaches, Memoization and tabulation.
Memoization code:-
class Solution {
public:
long long int nthFibonacci(long long int n){
int m=1000000007;
long long int a=0;
long long int b=1;
long long int c,i;
if(n==0){
return a;
}
for(i=2;i<=n;i++){
c=a%m+b%m;
a=b;
b=c;
}
return b%m;
}
};