Divide array A into K blocks and minimize the largest sum of any block.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/
- Time Complexity:
Solution:
Solution to Codility's Minimize Max Division problem which is from the Codility Lesson 14: Binary search algorithm and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to divide array a into k blocks and minimize the largest sum of any block. You can find the question of this MinMaxDivision problem in the Codility website.
package Codility.Lesson14;
import java.util.*;
public class MinMaxDivision {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 2, 1, 5, 1, 2, 2, 2 };
int result2 = solution(3, 5, a1);
System.out.println(result2);
}
public static int solution(int K, int M, int[] A) {
int min = 0;
int max = 0;
for (int i = 0; i < A.length; i++) {// get the sum as max, and the largest number as min
max += A[i];
min = Math.max(min, A[i]);
}
int result = max;
while (min <= max) {
int mid = (min + max) / 2;
System.out.println("mid: " + mid);
if (divisionSolvable(mid, K - 1, A)) {
max = mid - 1;
result = mid;
} else {
min = mid + 1;
}
}
return result;
}
private static boolean divisionSolvable(int mid, int k, int[] a) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
if (sum > mid) {
sum = a[i];
k--;
}
if (k < 0) {
return false;
}
}
return true;
}
}