Why incorrect answer for the Painter's partition problem when input is very large?

Question

I am solving GeeksforGeeks problem The Painter's Partition Problem-II :

Dilpreet wants to paint his dog's home that has n boards with different lengths. The length of i^th board is given by arr[i] where arr[] is an array of n integers. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board.

The problem is to find the minimum time to get this job done if all painters start together with the constraint that any painter will only paint continuous boards, say boards numbered {2,3,4} or only board {1} or nothing but not boards {2,4,5}.

Your task

Your task is to complete the function minTime() which takes the integers n and k and the array arr[] as input and returns the minimum time required to paint all partitions.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ k ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁵

My code:

    int findMax(int arr[],int n){
        int maxi=INT_MIN;
        for(int i=0;i<n;i++){
             maxi=max(maxi,arr[i]); 
        }
        return maxi; 
    }
    
    int sumOfAll(int arr[],int n){
        int sum=0;
        for(int i=0;i<n;i++){
             sum+=arr[i];
        }
        return sum;
    }
    
    int findPainters(int arr[],int n,int maxLength){
        // maxLength is the max length a painter can paint 
        int currLength=0; // currLength is the current length painted by current painter
        int painters=1; // no. of painters required
        for(int i=0;i<n;i++){
            if(currLength+arr[i]<=maxLength){
                // we can continue with the same painter
                currLength+=arr[i];
            }
            else{
                // currLength+arr[i]>maxLength
                // more painter required
                painters++;
                currLength=arr[i];
            }
        }
        return painters; // no. of painters required given a painter can paint maxLength length of board
    }
    
    long long minTime(int arr[], int n, int k)
    {
        // when no. of painters are more than or equal to no. of boards then 
        //each painter can paint a single board and max time taken to complete the task will 
        // be the maxLength board present in the array
        if(k>=n) return findMax(arr,n); 
        int low=findMax(arr,n); // min board length a painter atleast should be able to paint 
        int high=sumOfAll(arr,n); // max board length a painter could paint
        while(low<=high){
             int mid = low + (high - low) / 2;
            // mid define the max length a painter is able to paint or max Time taken by both painters
            // to complete the task
            // since each painter takes 1 unit time to paint 1 unit of the board. 
            int painters=findPainters(arr,n,mid);
            // while maintaining the maxLength mid , the painter required to paint are 
            if(painters<=k){
                // keep searching for min(maxTime taken)
                high=mid-1;
            }
            else{
                // increase the maxLength/maxTime to decrease the painter
                low=mid+1;
            }
        }
        return low;
    }

Most of the 200+ test cases pass, but for some very large inputs I get a completely different result. What could be the reason?

Answer 1

The algorithm is correct, but for large input the sums can exceed the range of int. As your function minTime has a return type of long long, use the same datatype for all sums and lengths:

• sumOfAll should have a long long sum and return long long
• findPainters should have a long long maxLength as last parameter, and its currLength variable should be long long too.
• In minTime, the variables low, high and mid should be long long.

With those fixes it should work.