Based on online solutions, I almost figured out how to solve Codility's MinMaxDivision, but there's one detail in the solution that I'm struggling to confirm.
The question is as follows:
Task description
You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.
You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.
The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.
The large sum is the maximal sum of any block.
For example, you are given integers K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2The array can be divided, for example, into the following blocks:
[2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15; [2], [1, 5, 1, 2], [2, 2] with a large sum of 9; [2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8; [2, 1], [5, 1], [2, 2, 2] with a large sum of 6.The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.
Write a function:
class Solution { public int solution(int K, int M, int[] A); }that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.
For example, given K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and K are integers within the range [1..100,000]; M is an integer
- within the range [0..10,000]; each element of array A is an integer
- within the range [0..M].
The following solution get's 100%:
public int solution(int K, int M, int[] A) {
int min = 0;
int max = 0;
for (int i = 0; i < A.length; i++) {
max += A[i];
min = Math.max(min, A[i]);
}
if (K == 1)
return max;
if (K >= A.length)
return min;
int result = min;
while (min <= max) {
int mid = (min + max) / 2;
if (check(mid, K, A)) {
max = mid - 1;
result = mid;
} else {
min = mid + 1;
}
}
return result;
}
private boolean check(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;
}
The idea of the solution is pretty simple: the minimum large sum is between min(A) or sum(A). Instead of iterating one by one, we can use binary search to look for the minimum large sum. For each candidate(mid), we see if we can have K blocks that does not pass the value of mid.
My question is about the strategy to find the number of blocks based on the mid value, in the check() method above. There are situations, where the number of blocks fits the criteria but none of the blocks have their sum equaling the mid value. One good example is when we have one block with all the array values, and the other blocks are empty.
One good example is A = [2, 3, 3, 5, 4, 2, 3], K = 3: the mid value eventually get's the value 10, we can have 3 blocks [2,3,3],[5,4],[2,3] but none of them are equal 10.
Can the solution algorithm output a mid value being the minimum large sum but that sum actually does not exist? How can the check() method always find the minimum large sum, AND that minimum large sum exists in the array without comparing the sum value with the mid value?
There are situations, where the number of blocks fits the criteria but none of the blocks have their sum equaling the mid value
This doesn't matter, because check will return true and a lower mid will be checked: some lower mid will eventually be one that will equal some block's sum.
One good example is A = [2, 3, 3, 5, 4, 2, 3], K = 3: the mid value eventually get's the value 10, we can have 3 blocks [2,3,3],[5,4],[2,3] but none of them are equal 10.
After mid = 10 and check returning true, this will execute:
max = mid - 1;
result = mid;
By setting max to 9, 9 will eventually be checked as well, and be returned.
Can the solution algorithm output a mid value being the minimum large sum but that sum actually does not exist?
No, because if that sum does not exist and check returns true, then we have a smaller sum that is possible - so the current mid is not the minimum. If the algorithm gets 100% then it will output this smaller value.
Also think about it in terms of the definition given in the problem statement:
The large sum is the maximal sum of any block.
[...]
The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.
So, by definition, the minimum large sum is the sum of some block.
How can the check() method always find the minimum large sum, AND that minimum large sum exists in the array without comparing the sum value with the mid value?
The check method itself does not find the minimum large sum. It only tells you if a given sum (its mid parameter) is valid (that is, if we can split the array into K blocks with a max sum <= mid).
It's the binary search that finds the minimum large sum.