Painter's Partitions Problem

help
,
1

Question


class Solution
{
    public:
    
    bool isPossible(int arr[], int n, int m, long long int mid){
        long long int sum=0; int cnt=1;
        for(int i=0; i<n; i++){
            if(arr[i]>mid) return false;
            if(sum+arr[i]>mid){
                sum = arr[i];
                cnt++;
                if(cnt>m) return false;
            }else{
                sum += arr[i];
            }
        }
        return true;
    }
    
    long long minTime(int arr[], int n, int k)
    {
        int sum=0; int mxm=0;
        for(int i=0; i<n; i++){
            sum += arr[i];
            mxm = max(mxm, arr[i]);
        }
        long long int strt = mxm; long long int end=sum;
        long long int ans = INT_MAX;
        while(end>=strt){
            long long int mid=  strt+(end-strt)/2;
            if(isPossible(arr, n, k, mid)){
                ans = min(ans, mid);
                end = mid-1;
            }else{
                strt = mid+1;
            }
        }
        return ans;
    }
};

I am not able to pass all the test case. Can’t figure out at what point I am going wrong

2

@roushan_17 please give this a try

3

sum will overflow as it can be up to 10^10 change it to long long int.

1 Like
4

Ohh yeah. I made others long long but missed that one.
By the way thanks @tejas10p

5

I see you already have your answer