# 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