algorithms/Java/PainterPartition.java at master · AASF-IIITM/algorithms

Repository navigation

public class Solution {

public int paint(int A, int B, ArrayList<Integer> C) {

long total = 0, max = Long.MIN_VALUE;

for(Integer c : C){

total += c;

max = Math.max(max,c);

}

long l = max, h = total;

while(l<h){

long mid = (l + (h-l)/2);

long reqPainters = getRequiredPainters(C,mid);

if(reqPainters <= A) h = mid;

else l = mid + 1;

}

long ans = ((l%10000003)*(B%10000003))%10000003;

return (int)ans;

}

public long getRequiredPainters(ArrayList<Integer> A , long k){

long total = 0, reqPainters = 1;

for(Integer a : A){

total += a;

if(total > k){

total = a;

reqPainters++;

}

return reqPainters;

}