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

Javascript version based on Codility binary search lesson: https://codility.com/media/train/12-BinarySearch.pdf

function solution(K, M, A) {
    let max = Number.MIN_SAFE_INTEGER, sum = 0;
    for (const a of A) {
        if (a > max) {
            max = a;
        }
        sum += a;
    }

    let start = max, end = sum;
    while (start <= end) {
        let mid = Math.floor((start + end)/2);
        if (check(A, mid) > K) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return start;
}

function check(A, max) {
    let sum = 0, k = 1;
    for (const a of A) {
        sum += a;
        if (sum > max) {
            k++;
            sum = a;
        }
    }
    return k;
}

Answer 2

I like László Papp's explanation. I have added a small optimization to block counting function and implemented in Python.

When count the blocks, if the temp result exceeds K then we don't need to continue figuring out an exact count, so we can just return K+1 and exit the function earlier.

#https://app.codility.com/demo/results/trainingJ3UZUR-7D6/
def count_block(K, A, L):
    """
    check how many blocks can be formed in array A such that each block has sum <= L
    if #block exceeds K then return (K+1)
    """
    temp_block_count = 1
    temp_sum = 0
    for n in A:
        if temp_sum + n > L:
            temp_block_count += 1
            if temp_block_count > K: 
                #need at least K+1 blocks to make each block has sum <= L (L is too small)
                return K + 1
            temp_sum = n
        else:
            temp_sum += n
    return K #need no more than K blocks with each block <= L (L could be too large)

def solution(K, M, A):
    start, end = max(A), sum(A)
    last_res = A[0]
    while start <= end:
        midval = (start + end) // 2
        division_formed = count_block(K, A, midval)
        if division_formed > K:           
            start = midval + 1
        else:
            #lower the search range
            end = midval - 1
            if division_formed == K:
                last_success = midval
    return last_success

Answer 3

Here is my code in Java, implemented based on László Papp's idea (https://stackoverflow.com/a/69910576/7688028):

    /**
     * Check if how many none-empty blocks could be created with given largeSum.
     * Note: largeSum is greater than all of a[i], because largeSum is in range [m, sumA]
     */
    private int countBlocks(int[] a, int largeSum) {
        int blocks = 0;
        int sumOfEachBlock = 0;
        for (int i = 0; i < a.length; i++) {
            if (sumOfEachBlock + a[i] > largeSum) {
                // this block cannot contains a[i], a[i] must belong to a new block
                sumOfEachBlock = 0;
                blocks++;
            }
            sumOfEachBlock += a[i];
        }

        // last block: there's no more a[i] left for it to calculate and check
        // whether "sumOfEachBlock + a[i] > largeSum" or not, so we need to check it here
        if (sumOfEachBlock <= largeSum)
            blocks++;

        return blocks;
    }

    /**
     * @param m not needed! Not used
     */
    public int solution(int k, int m, int[] a) {
        int sumA = 0;
        int maxA = -1;
        for (int i = 0; i < a.length; i++) {
            sumA += a[i];
            if (maxA < a[i])
                maxA = a[i];
        }

        int start = maxA, end = sumA;
        int mid, blocks;
        while (start <= end) {
            mid = (start + end) / 2;
            blocks = countBlocks(a, mid);
            if (blocks <= k) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }

Answer 4

Scored 100% on Codility (https://app.codility.com/demo/results/trainingQYJ68K-KJR/) using const midpoint = Math.floor((begin + end) / 2); instead of const midpoint = (begin + end) / 2; after copying Javascript code in answer by pytness (Nov 5, 2020 at 8:40).

/*
K = numberOfBlocks
M = maxNumber
A = array
*/

function solution(numberOfBlocks, maxNumber, array) {

    let begin = array.reduce((a, b) => (a + b), 0);  // Calculate total sum of A
    // console.log("total sum of A: ", begin);
    begin = Math.ceil(begin / numberOfBlocks);       // Calculate the mean of each theoretical block
    // console.log('Math.ceil(begin / numberOfBlocks): ', begin);
    begin = Math.max(begin, Math.max(...array));     // Set begin to the highest number in array if > than the mean
    // console.log('Math.max(begin, Math.max(...array)): ', begin);
    
    // In short: begin is now the smallest possible block sum


    // Calculate largest possible block sum
    let end = begin + maxNumber + 1;
    // console.log("end: ", end);
    var result = 0;

    while (begin <= end) {

        // Calculate the midpoint, which is our result guess
        const midpoint = Math.floor((begin + end) / 2);
        // console.log("midpoint: ", midpoint);
        
        let currentBlockSum = 0;
        let block = 1;

        for (let number of array) {
            currentBlockSum += number;
            // console.log("currentBlockSum: ", currentBlockSum);
            
            // If currentBlockSum > midpoint means that we are
            // in a different block...
            if (currentBlockSum > midpoint) {
                // console.log("currentBlockSum > midpoint");
                ++block;
                // console.log("block: ", block);
                
                // ...so we reset sum with the current number
                currentBlockSum = number;
                // console.log("currentBlockSum: ", currentBlockSum);
                
                // but if we are out of blocks, our guess (midpoint) is incorrect
                // and we will have to adjust it
                if (block > numberOfBlocks) {
                    // console.log("block > numberOfBlocks before break");
                    // console.log("block: ", block);
                    // console.log("break"); 
                    break;
                }
            }
        }


        // If we are out of blocks, it means that our guess for midpoint is too small.
        if (block > numberOfBlocks) {
            // console.log("block > numberOfBlocks before begin");
            begin = midpoint + 1;
            // console.log("begin: ", begin);
        }
        // Else, it's too big.
        else {
            // console.log("block <= numberOfBlocks");
            result = midpoint;
            // console.log("result: ", result);
            end = midpoint - 1;
            // console.log("end: ", end);
        }
    }

    // console.log("result: ", result);
    return result;
}

Answer 5

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 6

Looking and testing at the solutions, none of them actually work. I decided to spend some time on it, here is my solution (working for any use case with maximum performance).

using System;
using System.Linq;
class Solution
{
    public int solution(int K, int M, int[] A)
    {
        int start = Math.Max((int)Math.Ceiling((decimal)A.Sum()/(decimal)K), A.Max());
        int end = A.Sum();
        int result = 0;
        while(start <= end)
        {
            int dicotomie = (end + start) / 2;
            if(calculateNbBlocks(dicotomie, A) <= K)
            {
                result = dicotomie;
                end = dicotomie - 1;
            }
            else
                start = dicotomie + 1;
        }
        return result;
    }

    public int calculateNbBlocks(int dicotomie, int[] A)
    {
        int nbBlocks = 1;
        int sum = 0;
        for(int i=0; i<A.Length; i++)
        {
            sum += A[i];
            if(sum > dicotomie)
            {
                sum = A[i];
                nbBlocks++;
            }
        }
        return nbBlocks;
    }
}

Answer 7

I have changed a little bit the code so it's more clear, but here is my explanation:

/*
K = numberOfBlocks
M = maxNumber
A = array
*/

function solution(numberOfBlocks, maxNumber, array) {

    let begin = array.reduce((a, b) => (a + b), 0);  // Calculate total sum of A
    begin = Math.ceil(begin / numberOfBlocks);       // Calculate the mean of each theorethical block
    begin = Math.max(begin, Math.max(...array));     // Set begin to the highest number in array if > than the mean

    // In short: begin is now the smallest possible block sum


    // Calculate largest possible block sum
    let end = begin + maxNumber + 1;
    var result = 0;

    while (begin <= end) {

        // Calculate the midpoint, which is our result guess
        const midpoint = (begin + end) / 2;

        let currentBlockSum = 0;
        let block = 1;

        for (let number of array) {
            currentBlockSum += number;

            // If currentBlockSum > midpoint means that we are
            // in a different block...
            if (currentBlockSum > midpoint) {
                ++block;

                // ...so we reset sum with the current number
                currentBlockSum = number;

                // but if we are out of blocks, our guess (midpoint) is incorrect
                // and we will have to adjust it
                if (block > numberOfBlocks)
                    break;  
            }
        }


        // If we are out of blocks
        // it means that our guess (midpoint) is bigger than we thought
        if (block > numberOfBlocks) {
            begin = midpoint + 1;
        // else, it's smaller
        } else {
            result = midpoint;
            end = midpoint - 1;
        }
    }

    return result;
}

Answer 8

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.