4 months ago

Sourajeet Panda • 20

Bhubaneswar

import java.util.Arrays;

class GFG {
   static int[] dp;
   static int[] GCD2;
    static int maxgcd=1;
    static int gcd(int a, int b) {
        if (a < b) {
            // Swap a and b if a is less than b
            int temp = a;
            a = b;
            b = temp;
        }
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
    public static void solve(int[] arr) {
        dp = new int[arr.length];
        GCD2 = new int[arr.length];
        dp[0] = 1;
        GCD2[0] = arr[0];
       
        for (int i = 1; i < arr.length; i++) {
            int gcdi = gcd(arr[i], arr[i - 1]);
            if (GCD2[i-1] == gcdi) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 2;
            }
            if(gcdi>maxgcd)
            maxgcd=gcdi;
            GCD2[i] = gcdi;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {3, 6, 9, 18,36,6,18,36,54,36,54,9,3,63};
        int n=arr.length;
        solve(arr);System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(dp));
        System.out.println(Arrays.toString(GCD2));
        System.out.println(maxgcd);
        int ans=0;
        if (maxgcd==1)
        System.out.println(arr.length);
        for(int i=0;i<n;i++){
            if(GCD2[i]==maxgcd){
                ans=Math.max(ans,dp[i]);
            }
        }
        System.out.println(ans);
        
    }
}
this is my solution.....any mistake pointed is appreciated

7 months ago

unicornme707 • 20

Mumbai

https://www.geeksforgeeks.org/longest-sub-array-with-maximum-gcd/