N-th Fibonacci Number
You are given an integer ‘N’, your task is to find and return the N’th Fibonacci number using matrix exponentiation.

Since the answer can be very large, return the answer modulo 10^9 +7.

Fibonacci number is calculated using the following formula:

F(n) = F(n-1) + F(n-2), Where, F(1) = F(2) = 1.

For Example:

For ‘N’ = 5, the output will be 5.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow. The first line of each test case contains a single integer ‘N’, representing the integer for which we have to find its equivalent Fibonacci number.

Output Format:

For each test case, print a single integer representing the N’th Fibonacci number. Return answer modulo 10^9 + 7. Output for each test case will be printed in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

N-th Fibonacci Number

You are given an integer ‘N’, your task is to find and return the N’th Fibonacci number using matrix exponentiation.

Since the answer can be very large, return the answer modulo 10^9 +7.

Fibonacci number is calculated using the following formula:

F(n) = F(n-1) + F(n-2), 
Where, F(1) = F(2) = 1.

For Example:

For ‘N’ = 5, the output will be 5.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the integer for which we have to find its equivalent Fibonacci number.

Output Format:

For each test case, print a single integer representing the N’th Fibonacci number.

Return answer modulo 10^9 + 7.

Output for each test case will be printed in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5

Time Limit: 1 sec.

Follow Up:

Can you solve it in Time Complexity better than O(N)?

Accepted Answer

Find N-th Fibonacci number using matrix exponentiation and return modulo 10^9+7.

Implement a function to find N-th Fibonacci number using matrix exponentiation.
Return the answer modulo 10^9+7.
Use the formula F(n) = F(n-1) + F(n-2) with F(1) = F(2) = 1.
The time complexity should be better than O(N).
The constraints are 1 <= T <= 10 and 1 <= N <= 10^5.

Accepted Answer

Recursive Approach (TLE)

In this approach, we use recursion and uses a basic condition that :
- If ‘N’ is smaller than ‘1’(N<=1) we return ‘N’
- Else we call the function again as ninjaJasoos(N-1) + ninjaJasoos(N-2).
In this way, we reached our answer.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the given number.

As recursion uses a stack of size ‘N’

Time Complexity: O(2^n)Explanation:

O(2^N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our function will be called exponentially.

Accepted Answer

Dynamic Programming (TLE)

Ans of ‘i-th’ number is = ‘ans[i-1] + ans[i-2]’, so

With the help of dynamic programming, we try to store the previous value as the previous value leads to a solution.
So we use an array named as ‘dp’ of size ‘N+1’ to store the value.
On the first index of ‘dp[0]=0’ we store ‘0’ and on the first index of ‘dp[1]=1’ we store ‘1’.
Now run a loop and iterate through the “Nth”number like ‘dp[i]=dp[i-2]+dp[i-1]’.
dp[n] will contain the Fibonacci number of “Nth”number.
Return ‘dp[n]’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As we are using an array (dp) of size ‘N’ for storing values.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our loop will run for ‘N’ times.

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(N)



    Where 'N' reprents the "Nth" number .

*/



int fibonacciNumber(int n) {



    const int mod = 1e9 + 7;



    // Create an array to store solution.

    int dp[n + 1];



    dp[0] = 0;

    dp[1] = 1;



    // Iterate i from 2 to N and find ith Fibonacci Number.

    for (int i = 2; i <= n; i++) {

        dp[i] = (dp[i - 1] + dp[i - 2]) % mod;

    }



    // Return the Nth Fibonacci Number

    return dp[n];

}

Java (SE 1.8)

/*

    Time complexity: O(N)

    Space complexity: O(N) 



    Where 'N' reprents the "Nth" number .

*/



public class Solution {

    public static int fibonacciNumber(int n) {

        int mod = (int) 1e9 + 7;

        

        // Create an array to store solution

	    int[] dp = new int [n + 1];

	

	    dp[0] = 0;

	    dp[1] = 1;

	

	    // Iterate i from 2 to N and find ith Fibonacci Number 

	    for (int i = 2; i <= n; i++){

		    dp[i] = (dp[i - 1] + dp[i - 2]) % mod;

	    }

	

	    // Return the Nth Fibonacci Number

	    return dp[n];

    }



}

Python (3.5)

'''
    Time complexity: O(N)
    Space complexity: O(N) 

    Where 'N' reprents the "Nth" number .
'''

def fibonacciNumber(n):
    
    mod = int(1e9 + 7)

    # Create an array to store solution
    dp=[0 for i in range(n + 1)]
    dp[1] = 1
    
    # Iterate i from 2 to N and find ith Fibonacci Number 
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    
    # Return the Nth Fibonacci Number
    return dp[n]

Accepted Answer

Optimized Dynamic programming (TLE)

We take three integers a, b, c and we initialized a=0, b=1 as now we want to optimize the space by only storing “2” last numbers as we need only them.
Now we run a loop up to our “Nth” number and by using property the next number is the sum of two previous numbers like “c=a+b.
Now we update “a=b” and “b=c” at every step of the iteration.
In this way when our loop finished “b” contains the “Nth” Fibonacci number.
Return ‘b'.

Space Complexity: O(1)Explanation:

O(1), we are using constant space.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our loop will run for ‘N’ times.

Python (3.5)

'''
    Time complexity: O(N)
    Space complexity: O(1) 

    Where 'N' reprents the "Nth" number .
'''

def fibonacciNumber(n):
    
    mod = int(1e9 + 7)
    a = 0 
    b = 1 

    for i in range(2, n + 1):

        # The variable c stores the ith Fibonacci Number
        c = (a + b) % mod
    
        # Updating values of a and b
        a = b
        b = c
    
    # The variable b stores the Nth Fibonacci Number
    return b

Java (SE 1.8)

/*

    Time complexity: O(N)

    Space complexity: O(1) 



    Where 'N' reprents the "Nth" number .

*/



public class Solution {

    public static int fibonacciNumber(int n) {

        int mod = (int) 1e9 + 7;

        int a = 0;

        int b = 1;

        int c;



        for (int i = 2; i <= n; i++) {

            // The variable c stores the ith Fibonacci Number.

            c = (a + b) % mod;



            // Updating values of a and b.

            a = b;

            b = c;

        }



        // The variable b stores the nth Fibonacci Number.

        return b;

    }



}

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(1)



    Where 'N' represents the "Nth" number .

*/



int fibonacciNumber(int n) {

    int mod = (int) 1e9 + 7;



    int a = 0;

    int b = 1;

    int c;



    for (int i = 2; i <= n; i++) {



        // The variable c stores the ith Fibonacci Number.

        c = (a + b) % mod;



        // Updating values of a and b.

        a = b;

        b = c;

    }



    // The variable b stores the nth Fibonacci Number.

    return b;

}

Accepted Answer

Matrix Exponentiation

Observe that if we take the ‘N-1’th power of the matrix ‘COEF’ = [ [0, 1], [1, 1] ], then the bottom right element of the resultant matrix i.e ‘RESULT[1][1]’ will give the ‘N’th Fibonacci number.

More details can be found at the given link.

-----.html

Algorithm:

multiply function:
1. It will take two matrices as arguments and return the product of these two matrices.
Matrix_power function:
1. It will take a matrix and an integer ‘N’ as arguments and return the ‘N’th power of the matrix.
2. We will declare an identity matrix ‘RES’ of size 2x2.
3. Now while ‘N’ is not equal to 0
  1. If n is odd we will multiply the ‘COEF’ matrix with the ‘RES’.
  2. Then we will multiply the ‘COEF’ matrix with itself and divide ‘N’ by 2.
4. Finally, return the ‘RES’ matrix.
Given function:
1. We will declare the ‘COEF’ matrix.
2. Then we will calculate the ‘N-1’th power of the ‘COEF’ matrix and return the bottom right corner of the resultant matrix.

Space Complexity: O(logn)Explanation:

O(log(N)), where ‘N’ is the integer for which we have to find its equivalent Fibonacci number.

Extra space is used in the function call stack size.

Time Complexity: O(logn)Explanation:

O(log(N)), where ‘N’ is the integer for which we have to find its equivalent Fibonacci number.

Since we are calculating the power of the matrix in logarithmic time by continuously dividing ‘N’ by 2, the overall time complexity will be O(log(N)).

C++ (g++ 5.4)

/*

    Time Complexity: O(log(N)).

    Space Complexity: O(log(N)).



    Where 'N' is the given integer.

*/



// Function to multiply two matrices.

vector> multiply(vector> a,vector> b){



    const int mod = 1e9 + 7;

    

    // To store the resultant matrix.

    vector> c(2,vector(2,0));



    for(int i = 0; i < 2; i++){

        for(int j = 0; j < 2; j++){

            for(int k = 0; k < 2; k++){

                c[i][k] = (c[i][k] + (long long)((long long)a[i][j] * (long long)b[j][k])) % mod;

            }

        }

    }



    return c;

}



// Function to calclate n'th power of a matrix.

vector> matrix_power(vector> coef ,int n){



    // To store the resultant matrix.

    vector> res = {{1,0},{0,1}};



    // While loop till n > 0.

    while(n){

        // If n is odd, multiply res with coef.

        if(n % 2) res = multiply(res,coef);



        // Multiply coef with coef and update n to n/2.

        coef = multiply(coef,coef);

        n /= 2;

    }



    return res;



}





int fibonacciNumber(int n){



    // Declaring the coef matrix.

    vector> coef={{0,1},{1,1}};



    // Calculating the (n-1)th power of the coef matrix.

    vector> res = matrix_power(coef,n-1);



    // Return the bottom right element of the resultant matrix.

    return res[1][1];

}

Java (SE 1.8)

/*

    Time Complexity: O(log(N)).

    Space Complexity: O(log(N)).



    Where 'N' is the given integer.

*/



public class Solution{

    static int[][] multiply(int[][] a, int[][] b) {

        int mod = (int) (1e9 + 7);

        int[][] c = new int[2][2];

        for (int i = 0; i < 2; i++) {

            for (int j = 0; j < 2; j++) {

                c[i][j] = 0;

            }

        }

        for (int i = 0; i < 2; i++) {

            for (int j = 0; j < 2; j++) {

                for (int k = 0; k < 2; k++) {

                    c[i][k] = (int) ((c[i][k] + (long) ((long) a[i][j] * (long) b[j][k])) % mod);

                }

            }

        }



        return c;

    }



    // Function to calclate n'th power of a matrix.

    static int[][] matrix_power(int[][] coef, int n) {



        // To store the resultant matrix.

        int[][] res = {{1, 0}, {0, 1}};



        // While loop till n > 0.

        while (n > 0) {

            // If n is odd, multiply res with coef.

            if (n % 2 != 0) res = multiply(res, coef);



            // Multiply coef with coef and update n to n/2.

            coef = multiply(coef, coef);

            n /= 2;

        }



        return res;



    }



    public static int fibonacciNumber(int n) {

        int[][] coef = {{0, 1}, {1, 1}};



        // Calculating the (n-1)th power of the coef matrix.

        int[][] res = matrix_power(coef, n - 1);



        // Return the bottom right element of the resultant matrix.

        return res[1][1];





    }

}

Python (3.5)

'''
    Time Complexity: O(log(N)).
    Space Complexity: O(log(N)).

    Where 'N' is the given integer.
'''

def multiply(a, b):
    
    mod = int(1e9 + 7)
    c = [[0 for i in range(2)] for j in range(2)]
    
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][k] = (c[i][k] + a[i][j] * b[j][k]) % mod
                
    return c

# Function to calclate n'th power of a matrix.
def matrix_power(coef, n):
    
    # To store the resultant matrix.
    res = [[1, 0], [0, 1]]
    
    # While loop till n > 0.
    while n > 0:
        
        # If n is odd, multiply res with coef.
        if (n % 2 != 0):
            res = multiply(res, coef)
            
        # Multiply coef with coef and update n to n//2.
        coef = multiply(coef, coef)
        n //= 2
        
    return res

def fibonacciNumber(n):
    
    coef = [[0, 1], [1, 1]]
    
    # Calculating the (n-1)th power of the coef matrix.
    res = matrix_power(coef, n - 1)
    
    # Return the bottom right element of the resultant matrix.
    return res[1][1]

Top Capgemini Analyst interview questions & answers

Popular interview questions of Analyst

Top HR questions asked in Capgemini Analyst