Can anyone explain the problem?

#1

I tried to implement fast exponentiation using explanation fromarticle on geeksforgeeks but it shows error while solving:


Can anyone explain what’s wrong with the code?
I tried by computing fibronacci sum for last element of given range and fibronacci sum of element before beginning of range and subtracted them, but it shows tle and incorrect.

import java.util.*;
import java.io.*;

    class GFG {
        
        public static int fib(int n) {
            if(n<=1)
            return n;
            int f[][] = new int[][]{{1,1},{1,0}};
            int g = power(f,n-1);
            return g;
            
        }
        
        public static int power(int f[][],int n){
            int b[][] = new int[][]{{1,1},{1,0}};
            int sum = 1;
            for(int i = 2;i<=n;i++){
                multiply(f,b);
                sum = sum+f[0][0];
            }
            return((sum+1)%1000000007);
        }
        
        public static void multiply(int f[][],int b[][]){
            int x = f[0][0]*b[0][0]+f[0][1]*b[1][0];
            int y = f[0][0]*b[0][1]+f[0][1]*b[1][1];
            int z = f[1][0]*b[0][0]+f[1][1]*b[1][0];
            int w = f[1][0]*b[0][1]+f[1][1]*b[1][1];
            f[0][0] = x;
            f[0][1] = y;
            f[1][0] = z;
            f[1][1] = w;
            
        }
    	public static void main (String[] args) throws Exception {
    		Scanner s = new Scanner(System.in);
    		int t = s.nextInt();
    		for(int i = 1;i<=t;i++){
    		    int n = s.nextInt();
    		    int m = s.nextInt();
    		    if(n!=0)
    		        n = fib(n-1);
    		    m = fib(m);
    		   System.out.println((m-n)%1000000007);
    		    
    		}
    	}
    }
#2

Your approach is broadly correct. But you need to take care of few things to get it completely correct. This is what helped me solve this problem. Hope this helps you too.

  1. Your MOD operation is off. You need to MOD at the matrix multiplication level too.
  2. Can fib(n-1) - fib(m) be negative?
  3. Would “int” data type fit for all cases?
  4. In your solution, I feel there is slight index off error when you compute fibSum(M)-fibSum(N)
#3

How can fib(m)-fib(n-1)be negative? it is given in question that
0<=N<=M<=10^9
I revised my code. It still shows TLE

import java.util.*;
import java.io.*;

    class Main {
        
        public static long fib(long n) {
            if(n<=1)
            return n;
            long f[][] = new long[][]{{1,1},{1,0}};
            long g = power(f,n-1);
            return g;
            
        }
        
        public static long power(long f[][],long n){
            int b[][] = new int[][]{{1,1},{1,0}};
            long sum = 1;
            for(int i = 2;i<=n;i++){
                multiply(f,b);
                sum = sum+f[0][0];
            }
            return((sum+1)%1000000007);
        }
        
        public static void multiply(long f[][],int b[][]){
            long x = (f[0][0]*b[0][0]+f[0][1]*b[1][0])%1000000007;
            long y = (f[0][0]*b[0][1]+f[0][1]*b[1][1])%1000000007;
            long z = (f[1][0]*b[0][0]+f[1][1]*b[1][0])%1000000007;
            long w = (f[1][0]*b[0][1]+f[1][1]*b[1][1])%1000000007;
            f[0][0] = x;
            f[0][1] = y;
            f[1][0] = z;
            f[1][1] = w;
            
        }
    	public static void main (String[] args) throws Exception {
    		Scanner s = new Scanner(System.in);
    		int t = s.nextInt();
    		for(int i = 1;i<=t;i++){
    		    long n = s.nextLong();
    		    long m = s.nextLong();
    		    if(m==n){
                System.out.println(fib(n)%1000000007);
    		        continue;
    		    }
    		    if(n!=0)
    		        n = fib(n-1);
    		    if(m!=0)
    		        m = fib(m);
    		    System.out.println((m-n)%1000000007);
    		    
                
    		}
    	}
    }
#4

Never mind. Solved it