Print a particular nth Fibonacci number in C++ up to range 10^18
In this tutorial, we are going to learn how to print a particular Fibonacci number up to range 10^18 in C++. We are going to use a hash map for this particular problem. As we know we cannot use an array for storing so many values so using the hash map is a proper choice for this particular type of problem.
Consider fib(n) to be the (n+1) th Fibonacci number. We will have two cases when n is even and another one when n is odd. Consider a variable k which is equal to n/2.
For the first case when n is even we will use this relation :
- fib(n) = fib(k)*fib(k) + fib(k-1)*fib(k-1)
For the second case when n is odd we will use this relation :
- fib(n) = fib(k)*fib(k+1) + fib(k-1)*fib(k)
Lets try to implement our above idea to get the solution of this problem.
Program to print a particular Fibonacci number in C++
Cpp source code:
// Program to print a particular Fibonacci number #include<bits/stdc++.h> using namespace std; // Declaring hashmap map<long long int ,long long int>F; int fib(long long int n) { if(F.count(n)) // Checking if we have already calcuted that Fibonacci number { return F[n]; } long long int k=n/2; if(n%2==0) { return F[n]=(fib(k)*fib(k)+fib(k-1)*fib(k-1))%1000000007; } else { return F[n]=(fib(k)*fib(k+1)+fib(k-1)*fib(k))%1000000007; } } // Driver Code int main() { long long int n; cout<<"Enter the ith number: "; cin>>n; F[0]=F[1]=1; cout<<"\nThe "<<n << " th Fibonacci number is "<<fib(n-1)<<"\n"; return 0; }
Input/Output:
Enter the ith number: 10000 The 10000 th Fibonacci number is 910095538
- Time Complexity of this code is O( log n * log log n ).
You may also learn,
check if a given matrix is sparse or not in C++
Solution of Tower Of Hanoi Problem in C++
Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.
Leave a Reply