How to solve codility minMaxDivision

Question

I have been trying to wrap my head around this codility question for 1H30,and how to solve with binary search. I found the answer but I cant understand the logic behind it. Can someone who gets it kindly walk me through this answer.

This is the question

Task description

You are given integers K, M and a non-empty zero-indexed 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] = 2

The 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:

function solution(K, M, A);

that, given integers K, M and a non-empty zero-indexed 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] = 2

the function should return 6, as explained above.

Assume that:

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].

This is the answer I could get my hands on

function solution(K, M, A) {
    var begin = A.reduce((a, v) => (a + v), 0)
    begin = parseInt((begin+K-1)/K, 10);
    var maxA = Math.max(A);
    if (maxA > begin) begin = maxA;

    var end = begin + M + 1;
    var res = 0;

    while(begin <= end) {
        var mid = (begin + end) / 2;
        var sum = 0;
        var block = 1;
        for (var ind in A) {
            var a = A[ind];
            sum += a;
            if (sum > mid) {
                ++block;
                if (block > K) break;
                sum = a;
            }
        }
        if (block > K) {
            begin = mid + 1;
        } else {
            res = mid;
            end = mid - 1;
        }
    }
    return res;
}

Answer 1

I would like to give the more detailed explanation of the algorithm that I have implemented and then one correct implementation in C++.

Find the maximum element in the input array. We could also use M, but M does not necessarily occur. A smaller number could be the maximum, so it is slight optimisation.

Calculate the sum of the input array. This would be the maximum largest sum.

Apply binary search, where the start is the maximum element and the end is the sum. The minimum largest sum would be in this range.

For each trial, check whether we can squeeze the elements into fewer blocks than the block number requested. If it is fewer, it is okay because we can use empty blocks. If it is equal, that is also acceptable. However, it is greater, then we can conclude that the tried minimum largest sum needs to be higher to allow individual blocks to be larger to reduce the block count.

One general principle can be observed above that the more fairly we distribute the sums of the blocks, the largest will become the minimum possible. For this, we need to squeeze as many elements into an individual block as possible.

If the number of blocks for a tried minimum largest sum is smaller than the expected block count, then we can try a slightly smaller minimum largest sum, otherwise we have to try a bit greater until we eventually find the best number.

As far as runtime complexity goes, the solution is O(n * log(N * M)) because the binary search is logarithmic. The sum can be N number of times the maximum element M at worst, which results in an N * M range to bisect with binary search. The inner iteration will go through all the elements, so that is N times. Therefore, it is O(N * log(N * M)) which is equivalent to O(N * log(N + M).

int check(vector<int>& A, int largest_sum)                                      
{                                                                               
  int sum = 0;                                                                  
  int count = 0;                                                                
  for (size_t i = 0; i < A.size(); ++i) {                                       
    const int e = A[i];                                                         
    if ((sum + e) > largest_sum) { sum = 0; ++count; }                          
    sum += e;                                                                   
  }                                                                             
                                                                                
  return count;                                                                 
}                                                                               
                                                                                
int solution(int K, int /*M*/, vector<int> &A)                                  
{                                                                               
  int start = *max_element(A.begin(), A.end());                                 
  int end = accumulate(A.begin(), A.end(), 0);                                  
  while (start <= end) {                                                        
    int mid = (start + end) / 2;                                                
    if (check(A, mid) < K) end = mid - 1;                                       
    else start = mid + 1;                                                       
  }                                                                             
  return start;                                                                 
} 

Answer 2

This is a binary search on the solution. For each candidate solution, we iterate over the whole array once, filling array blocks to the maximum sum the block can be before exceeding the candidate. If the sum is not achievable, there is no point in trying a smaller sum so we search the space of higher possible candidates. And if the sum is achievable, we try the space of lower candidates, while we can.