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
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;
    return F[n]=(fib(k)*fib(k)+fib(k-1)*fib(k-1))%1000000007;
    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: ";
  cout<<"\nThe "<<n <<  " th Fibonacci number is "<<fib(n-1)<<"\n";
  return 0;


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

Your email address will not be published. Required fields are marked *