Find the maximum value of G that can be obtained after K splits ( IMPORTANT QUE )

https://practice.geeksforgeeks.org/problems/2b70d42632a4e207569c6d2d777383e4603d6fe1/1

You are given an array, arr of length N, and also a single integer K . Your task is to split the array arr into K non-overlapping, non-empty subarrays. For each of the subarrays, you calculate the sum of the elements in it. Let us denote these sums as S1, S2, S3, ..., Sk. Where Si denotes the sum of the elements in the ith subarray from left.

Let G = GCD( S1, S2 ,S3 , ..., Sk).

Find the maximum value of G that can be obtained.
The array may contain duplicate elements.

Example 1:
Input:
N = 5
K = 4
arr[] = {6, 7, 5, 27, 3}
Output: 3

Explanation:
Since K = 4, you have to split the array into 4 subarrays.
For optimal splitting, split the array into
4 subarrays as follows: [[6], [7, 5], [27], [3]]
Therefore, S1 = 6, S2 = 7 + 5 = 12, S3 = 27, S4 = 3
Hence, G = GCD(S1, S2, S3, S4) = GCD(6, 12, 27, 3) = 3
It can be shown that 3 is the maximum value of G that can be obtained.
Thus, the answer is 3.


Example 2:
Input:
N = 3
K = 2
arr[] = {1, 4, 5}
Output: 5

Explanation:
Since K = 2, you have to split the array into 2 subarrays.
For optimal splitting, split the array into
2 subarrays as follows: [[1, 4], [5]]
Therefore, S1 = 1 + 4 = 5, S2 = 5
Hence, G = GCD(S1, S2) = GCD(5,5) = 5
It can be shown that 5 is the maximum value of G that can be obtained.
Thus, the answer is 5.



Expected Time Complexity: O(N * x)
Expected Auxiliary Space: O(x), x is the number of factors of the sum of all elements.

Constraints:

1 <= N <= 10^4
1 <= K <= N
1 <= arr[i] <= 10^5

---------------------------------------------------------------------------------------------------------------------------------------

BRUTE FORCE (TLE❌❌❌❌❌❌)

class Solution {
  public:
    vector<vector<int>> dp;

    int helper(vector<int> &arr, int curr, int n, int k){
        if(k==0 && curr==n){
            return 0;
        }
        if(curr==n || k==0){
            return INT_MIN;
        }
        if(dp[curr][k]!=-1){
            return dp[curr][k];
        }
        int sum=0;
        int res=INT_MIN;
        for(int i=curr;i<n;i++){
            sum+=arr[i];
            int temp=helper(arr,i+1,n,k-1);
            if(temp==INT_MIN){
                continue;
            }
            res=max(res,__gcd(temp,sum));
        }
        return dp[curr][k]=res;
    }

    int solve(int N, int K, vector<int> &arr) {
        dp.resize(N+1,vector<int>(K+1,-1));
        return helper(arr,0,N,K);
    }
};

---------------------------------------------------------------------------------------------------------------------------------------

OPTIMISED (ACCEPTED✅✅✅✅)

class Solution {
  public:
    int solve(int N, int K, vector<int> &arr) {
        int sum=0;
        for(int i=0;i<N;i++){
            sum+=arr[i];
        }

        vector<int> factors;  // GENERATE ALL FACTORS
        for(int i=1;i*i<=sum;i++){
            if(sum%i==0){
                factors.push_back(i);
                if(i!=sum/i){
                    factors.push_back(sum/i);
                }
            }
        }

        int ans=1;
        for(auto f: factors){
            int count=0;
            int currsum=0;
            for(int i=0;i<N;i++){
                currsum+=arr[i];
                if(currsum%f==0){
                    count++;
                    currsum=0;
                }
            }
            if(count>=K){
                ans=max(ans,f);
            }
        }
        return ans;
    }
};