@harsh-govind I have written the same solution in java but got the wrong result. For instance, n =4 got result as 9. Please correct the solution. public class SumOfNFibonnaci { public int[][] sum(int[][] mat, int nNumber) { if(nNumber == 1) return mat; int[][] tempM = sum(mat, nNumber/2); if(nNumber%2 == 0) return matMultiply(tempM, tempM); else return matMultiply(tempM, matMultiply(tempM,mat)); } public int[][] matMultiply(int[][] mA, int[][] mB){ int[][] mM = {{1, 1},{1,0}}; for(int i =0; i < 2; i++) { for(int j =0; j < 2; j++) { for(int k =0; k < 2; k++) { mM[i][j] += (mA[i][k]*mB[j][k])%1000000009; } } } return mM; } public static void main(String[] args) { // TODO Auto-generated method stub int n= 4; //1,1,2,3 int[][] mat = {{1, 1},{1,0}}; SumOfNFibonnaci sumOfNFibonnaci = new SumOfNFibonnaci(); int[][] res = sumOfNFibonnaci.sum(mat, n); System.out.println("res: "+ res[0][1]%1000000009); } }
I don't know why people said its a good explanation but I know this is worst explanation and just wasted my 22 minutes on this I am sorry to say but your speed is 1.5 x