Java_Programs-CodingNinjas/N-th_Fibonacci_Number.java at main · hey-its-d2t2/Java_Programs-CodingNinjas · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
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:
For ‘N’ = 5, the output will be 5.

*/

import java.util.*;

public class Solution {
    static final int MOD = 1000000007;

    public static int fibonacciNumber(int n) {

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

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


        return res[0][0];

    }


    public static int[][] matrixPower(int[][] coef, int n) {

        if (n == 0)

            return new int[][]{{1, 0}, {0, 1}};


        int[][] res = matrixPower(coef, n / 2);


        if (n % 2 == 1) {

            res = multiply(multiply(res, res), coef);

        } else {

            res = multiply(res, res);

        }


        return res;

    }


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

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


        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)a[i][j] * b[j][k]) % MOD);

                }

            }

        }

        return c;

    }

}