Problem

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

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

Note:

The blocks are not necessarily of the same size (length). The number of blocks is K. In the example data above, K is 3.

An empty block is a block of zero length (width of zero). Such a block has no element and its block sum is 0. A quotation from the problem description is, "Every element of the array should belong to some block." This does not mean that every block has at least one element. 

Another quotation from the problem description is:

“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.” 

For the 3 blocks:

        [2, 1, 5, 1, 2, 2, 2], [], [] 

the large sum is: 2 +1 + 5 + 1 + 2 + 2 + 2 = 15. In fact, this is the maximum large sum.

For the 3 blocks: 

        [2], [1, 5, 1, 2], [2, 2]

the large sum is: 1 +5 + 1 + 2 = 9. 

For the 3 blocks:

        [2, 1, 5], [], [1, 2, 2, 2] 

the large sum is: 2 + 1 + 5 = 8.

For the 3 blocks: 

        [2, 1], [5, 1], [2, 2, 2]

the large sum is: 2 +2 + 2 = 6, which is actually the minimum large sum. 

No matter how the given list is divided into three again, there will be no large sum less than 6. This is important. For example, in the division,

[2, 1], [5, 1, 2], [2, 2] 

the large sum is 5 + 1 + 2 = 8. There is another division (above) with the same large sum of 8, which is not less than 6. As another example, in the division,

[2], [1, 5, 1, 2, 2], [2] 

the large sum is 1 + 5 + 1 + 2 + 2 = 11, which is greater than 9 (above), but less than 15 (above). And 11 is definitely not less than 6.

All the large sums determined so far, arranged in ascending order are: 

    6, 8, 9, 11, 15

At this point, it looks as if, if all the large sums are determined and arranged in ascending order, the least sum can just be taken as the answer; assuming all that is done fast. That is a good idea, but it is not good enough.

Maximum and Minimum Block Sums

Number of elements, N in the example data given above is 7. The example question says that K is 3 and M is 5, and no element in the given array is more than 5. Also, from the assumption, there is no number less than 0. This means that the largest possible block (slice) sum for any possible block (the whole array), should be considered as: 

    5 + 5 + 5 + 5 + 5 + 5 + 5 = 5 x 7 = 35

The smallest block sum for any possible block is: 

    0 + 0 + 0 + 0 + 0 + 0 + 0 = 0 x 7 = 0

So, for the test cases at app.codility.com/programmers the maximum block sum is taken as M x N and the minimum block sum is taken as 0. 

All Block Sums

From the given data above, whether a block among the 3 blocks is the maximum block sum or not, any block sum can have a value between 0 and 35 (inclusive). Of course, based on the particular dataset, some block sums (e.g. 14 for above data) will not exist.

The following table shows all the possible block sums that can be determined (in theory) from any such given data (of the problem):

Notice that the index for each block sum, is the same as the block sum. There is no way the sum of any block above (given data), can be 14; so the cell for index 14 is empty. However, 14 as a block sum still has to be considered in the analysis (see below). It is known in advance, that the block sum required is 6. This means that, no matter how the given whole list can be divided into 3, the sum for the minimum large sum cannot be less than 6. So, if all the possible block sums can be presented in ascending order, then the index of the minimum large sum may be obtained using binary search algorithm, to arrive at index 6 (see below). The index is automatically that for the minimal large sum (index and value are the same in the table). And that is the approach used below. 

In fact, in the analysis below, it is assumed that each of the values from 0 to 35 (MxN) is a block sum, as in the following table (same as above):

The Program

There are two functions: solution() and tryLargeSum() . solution() does binary search algorithm. tryLargeSum() determines if the given list can be divided into K (3) blocks, where at least one block has the large sum whose value is the current middle term of the binary search solution() function. 

The program is presented first, before its explanation. Read through the program first before reading the explanation below

<script type='text/javascript'>
    "use strict";    

    function tryLargeSum(A, maxblockscount, mid) {    //possibility
        //maxblockscount is K

        let sum=0;
        let blockscount=1;    //non-empty array A
        let size = A.length;
    
        for (let i=0; i<size; i++) {
            if (A[i]>mid)
                return false;    //not possible for one element to be greater than any largest sum.
    
            sum += A[i];
            if (sum > mid){
                blockscount++;
                if (blockscount > maxblockscount) 
                    return false;
                sum = A[i];
            }
        }
    
        if (blockscount > maxblockscount) 
            return false;
        
        return true;
    }

    function solution(K, M, A) {    //binary search
        let N = A.length;
    
        let loIndex = 0;    //least blocks sum
        let hiIndex = M * N;    //maximum blocks sum
        let midIndex;
    
        let result = hiIndex;    //large sum beginning at maximum, then downwards
    
        while(loIndex <= hiIndex){
            midIndex=parseInt((loIndex + hiIndex)/2);
        
            if (tryLargeSum(A, K, midIndex)==true){
                hiIndex = midIndex - 1;
                if (midIndex < result)
                   result = midIndex;    //index and value are same
            }else{
                loIndex = midIndex + 1;
            }
        }
        return result;
    }


    let A = [2, 1, 5, 1, 2, 2, 2];

    let ret = solution(3, 5, A);

    document.write(ret + '<br>');

</script>

Illustration

Since each of the numbers from 0 to MxN is a possible block (slice) sum, there is no need to waste operations (ending up with a longer time complexity) to produce all the different possible slice sums (from the given data). They are already there (assumed), though not coded, from 0 to MxN (35). 

The illustration in this section is done with the given data above:

    A = [2, 1, 5, 1, 2, 2, 2]; 

The table to use is:

Begin with the maximum possible large sum, 35 from the table. (loIndex = 0; here. See below).  If the minimum large sum is 35, would it be possible to divide the given list into 3 (K) blocks, even if some blocks have zero width. To verify this, begin with the given list at index 0 with its value of 2. 

The beginning sum for the first block is 0. Is 2 greater than 35, the tentative minimum large sum? - No. So the first block sum should be 0 + 2 = 2 for given list index 0. Is the next number 1, from the given array greater than 35? - No. So the first block sum should be 0 + 2 + 1 = 3 for list indexes 0 and 1. Is the next number 5, from the given array, greater than 35? - No. So the first block sum should be 0 + 2 + 1 + 5 = 8 for list indexes 0, 1, 2. Is the next number 1, from the given array, greater than 35? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 = 9 for list indexes 0, 1, 2, 3. Is the next number 2, from the given array, greater than 35? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 + 2 = 11 for list indexes 0, 1, 2, 3, 4. Is the next number 2, from the given array, greater than 35? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 + 2 + 2 = 13 for list indexes 0, 1, 2, 3, 4, 5. Is the next number 2, from the given array, greater than 35? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 + 2 + 2 + 2 = 15 for list indexes 0, 1, 2, 3, 4, 5, 6 (end of given list). With that, there are two more blocks of 0 width each. With a minimum tentative large sum of 35, and the given list above, it is not possible to have 3 blocks, even with 2 blocks of 0 width. The sum of the full list given above, is actually 15. So, if the minimum large sum is 35, it would not be possible to divide the given list into 3 (K) blocks, even if some blocks have zero width; as 35 is greater than the sum of the whole given list. Note that if a single element in the given list was greater than 35, it would not be possible to have the distribution: [2, 1, 5, 1, 2, 2, 2], [], [] , which is still wrong.

The values of the table list are the same as the table's indexes, from 0 to 35. Since the highest sum of 15 from the given list is not up to 35, which is the first tentative minimum large sum, then the actual minimum large sum, is somewhere down in the table list. Next, try half of the last tentative value from the table list, as the new tentative value. And this is binary search beginning in action, somewhat. The above loop (with its iterations) is ended. 

A new loop begins with 17 as the next binary search target value. 35 divided by 2 is 17½. By integer division, 17 is taken (the fraction is abandoned), since array A consists of integers. 17 from the table list, is the new tentative minimum large sum (at this point). (loIndex = 0; here. See below).

Beginning again from index 0 with value 2 of the given array: If 17 is the minimum large sum, will it be possible to divide the given list into 3 blocks, not necessarily of equal widths, and some may be of zero width, so that at least one of the blocks has a sum of 17, and the other sums are either 17 or below? - Well, that is to be verified, from the given list, beginning from index 0, with its value, 2. The beginning sum for the first block of this loop is 0. Is 2 greater than 17, the tentative minimum large sum? - No. So the first block sum should be 0 + 2 = 2 for given list index 0. Is the next number 1, from the given array (list) greater than 17? - No. So the first block sum should be 0 + 2 + 1 = 3 for list indexes 0 and 1. Is the next number 5, from the given array, greater than 17? - No. So the first block sum should be 0 + 2 + 1 + 5 = 8 for list indexes 0, 1, 2. Is the next number 1, from the given array, greater than 17? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 = 9 for list indexes 0, 1, 2, 3. Is the next number 2, from the given array, greater than 17? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 + 2 = 11 for list indexes 0, 1, 2, 3, 4. Is the next number 2, from the given array, greater than 17? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 + 2 + 2 = 13 for list indexes 0, 1, 2, 3, 4, 5. Is the next number 2, from the given array, greater than 17? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 + 2 + 2 + 2 = 15 for list indexes 0, 1, 2, 3, 4, 5, 6 (end of given list). With that, there are two more blocks of 0 width each. With a minimum tentative large sum of 17, and the given list above, it is not possible to have 3 blocks, even with 2 blocks of 0 width. The sum of the full list given above, is actually 15. So, if the minimum large sum is 17, it would not be possible to divide the given list into 3 (K) blocks, even if some blocks have zero width; as 17 is greater than the sum of the whole given list. Note that if a single element in the given list was greater than 17, it would not be possible to have the distribution: [2, 1, 5, 1, 2, 2, 2], [], [] , which is still wrong. 

The values of the table list are the same as the table's indexes, from 0 to 35. Since the highest sum of 15 from the given list is not up to 17, which is the second tentative minimum large sum, then the actual minimum large sum, is somewhere down in the table list. Next, try half of the last tentative value from the table list, as the new tentative value. And this is binary search continuing in action, somewhat. The above loop (with its iterations) is ended.

A new loop begins with 8 as the next binary search target value. 17 divided by 2 is 8½. By integer division, 8 is taken (the fraction is abandoned), since array A consists of integers. 8 from the table list, is the new tentative minimum large sum (at this point). (loIndex = 0; here. See below). 

Beginning again from index 0 with value 2 of the given array: If 8 is the minimum large sum, will it be possible to divide the given list into 3 blocks, not necessarily of equal widths, and some may be of zero width, so that at least one of the blocks has a sum of 8, and the other sums are either 8 or below? - Well, that is to be verified, from the given list, beginning from index 0, with its value, 2. The beginning sum for the first block of this loop is 0. Is 2 greater than 8, the tentative minimum large sum? - No. So the first block sum should be 0 + 2 = 2 for given list index 0. Is the next number 1, from the given array (list) greater than 8? - No. So the first block sum should be 0 + 2 + 1 = 3 for list indexes 0 and 1. Is the next number 5, from the given array, greater than 8? - No. So the first block sum should be 0 + 2 + 1 + 5 = 8 for list indexes 0, 1, 2. Is the next number 1, from the given array, greater than 8? - No. So the first block sum should be 0 + 2 + 1 + 5 + 1 = 9 for list indexes 0, 1, 2, 3. Notice at this point that the running sum of the first block is greater than 8. So, instead of going to the next iteration with the next number in the given list (array), the first block has to end, for the next blocks to begin with their own running sums. The first block ends at index 2 with the sum of 8, and the second block starts at index 3 with value, 1. This is because the tentative minimum large sum is 8, and no block should have a sum above 8. The sum for the second block starts at index 3 with value, 1 and not 0. Is the next number 2 (second number of the second block), from the given array, greater than 8? - No. So the second block sum should be 1 + 2 = 3 for list indexes 3, 4. Is the next number 2 (of next iteration), from the given array, greater than 8? - No. So the second block sum should be 1 + 2 + 2 = 5 for list indexes 3, 4, 5. Is the next number 2, from the given array, greater than 8? - No. So the second block sum should be 1 + 2 + 2 + 2 = 7 for list indexes 3, 4, 5, 6 (end of given list). With that, there is one more block of 0 width. With a minimum tentative large sum of 8, and the given list above, it is possible to have 3 blocks, with 1 block of 0 width. And so, its distribution: [2, 1, 5], [1, 2, 2, 2], [] looks like the correct answer.

To be sure if [2, 1, 5], [1, 2, 2, 2], [] is the correct answer with minimal large sum of 8, the binary search algorithm has to complete in O(lon₂n) time. The loops in determining the different blocks, also take more time. 

The values of the table list are the same as the table's indexes, from 0 to 35. The binary search algorithm has not yet reached its end. To know if a number less than 8 is the minimum large sum, next, try half of the last tentative value from the table list, as the new tentative value. And this is binary search continuing in action, somewhat. The above loop (with its iterations) is ended.

A new loop begins with 4 as the next binary search target value. 8 divided by 2 is 4. Four from the table list, is the new tentative minimum large sum (at this point). (loIndex = 0; here. See below). 

Beginning again from index 0 with value 2 of the given array: If 4 is the minimum large sum, will it be possible to divide the given list into 3 blocks, not necessarily of equal widths, and some may be of zero width, so that at least one of the blocks has a sum of 4, and the other sums are either 4 or below? - Well, that is to be verified, from the given list, beginning from index 0, with its value, 2. The beginning sum for the first block of this loop is 0. Is 2 greater than 4, the tentative minimum large sum? - No. So the first block sum should be 0 + 2 = 2 for given list index 0. Is the next number 1, from the given array (list) greater than 4? - No. So the first block sum should be 0 + 2 + 1 = 3 for list indexes 0 and 1. Is the next number 5, from the given array, greater than 5? - Yes. At this state, there is no point continuing the loop, because there can be no block, even of one element, whose sum is greater than 4, which is the new tentative minimum large sum. This loop with its binary search tentative target value of 4, has failed (and the tryLargeSum() function should return false).

The previous binary search interval, with its target value of 4 is from 0 (loIndex) to 8 (hiIndex). The target value of 4 was obtained while going downwards (leftwards) in the possible block sums (theoretical) table. So the next target to try should be on the right (upper-side) of 4, which is half the value from 4 to 8. That is, the next (loIndex + hiIndex)/2 = (4 + 8)/2 = 6. The above loop (with its iterations) is ended. 

A new loop begins with 6 as the next binary search target value. Beginning again from index 0 with value 2 of the given array: If 6 is the minimum large sum, will it be possible to divide the given list into 3 blocks, not necessarily of equal widths, and some may be of zero width, so that at least one of the blocks has a sum of 6, and the other sums are either 6 or below? - Well, that is to be verified, from the given list, beginning from index 0, with its value, 2. The beginning sum for the first block of this loop is 0. Is 2 greater the 6, the tentative minimum large sum? - No. So the first block sum should be 0 + 2 = 2 for given list index 0. Is the next number 1, from the given array (list) greater than 6? - No. So the first block sum should be 0 + 2 + 1 = 3 for list indexes 0 and 1. Is the next number 5, from the given array, greater than 6? - No. So the first block sum should be 0 + 2 + 1 + 5 = 8 for list indexes 0, 1, 2. Notice at this point that the running sum of the first block is greater than 6. So, instead of going to the next iteration with the next number in the given list (array), the first block has to end, for the next blocks to begin with their own running sums. The first block ends at index 1 with the sum of 3, and the second block starts at index 2 with value, 5. This is because the tentative minimum large sum is 6, and no block should have a sum above 6. The sum for the second block starts at index 2 with value, 5 and not 0. Is the next number 1 (second number of the second block), from the given array, greater than 6? - No. So the second block sum should be 5 + 1 = 6 for list indexes 2, 3. Is the next number 2 (of next iteration), from the given array, greater than 6? - No. So the second block sum should be 5 + 1 + 2 = 8 for list indexes 2, 3, 4. Notice at this point that the running sum of the second block is greater than 6. So, instead of going to the next iteration with the next number in the given list (array), the second block has to end, for the next blocks to begin with their own running sums. The second block ends at index 3 with the sum of 6, and the second block starts at index 4 with value, 2. This is because the tentative minimum large sum is 6, and no block should have a sum above 6. The sum for the third block starts at index 4 with value, 2 and not 0. Is the next number 2 (of next iteration), from the given array, greater than 6? - No. So the third block sum should be 2 + 2 = 4 for list indexes 4, 5. Is the next number 2 from the given array, greater than 6? - No. So the third block sum should be 2 + 2 + 2 = 6 for list indexes 4, 5, 6 (end of given list). With that, there is no more block. The number of blocks (K) is now 3. This looks like the answer. It is better than the previous appeared answer of 8. And so, its distribution: [2, 1], [5, 1], [2, 2, 2] looks like the correct answer with minimum large sum of 6, a better answer to [2, 1, 5], [1, 2, 2, 2], [] with minimum large sum of 8.

It is known in advance that the distribution, [2, 1], [5, 1], [2, 2, 2] is the correct answer (with minimum large sum of 6). However, the binary search algorithm, does not know that it is the correct answer. The binary search algorithm can only know the correct answer when it ends in O(log₂n) time. Do not forget that the loops for the block sets, add extra time. The binary search algorithm ends when the interval is 0 (i.e. hiIndex - loIndex = 0) To be sure that [2, 1], [5, 1], [2, 2, 2] is the correct answer with minimal large sum of 6, the binary search algorithm has to complete in O(lon₂n) time. This loop and the binary search target value of 6 has not failed. So the search has to continue downwards (leftwards) in the possible block sums table. 

The previous binary search interval, with its target value of 6 is from 4 (loIndex) to 8 (hiIndex). The target value of 6 was obtained while going upwards (rightwards) in the possible block sums (theoretical) table. Since that did not fail, the next target to try should be on the left (lower-side) of 6, which is half the value from 4 to 6. This is going downwards (leftwards) since the previous loop and its binary search target of 6 did not fail. That is, the next (loIndex + hiIndex)/2 = (4 + 6)/2 = 5. Between 4 and 6 is only one number, which is 5. The binary search ends with the target of 5. If 5 does not work as the minimum large sum, then the previous minimum large sum of 6 is the answer, and has to be returned.

The values of the table list are the same as the table's indexes, from 0 to 35. The binary search algorithm has not yet reached its end. To know if a number less than 6 is the minimum large sum, next, try the integer at half of the last interval from the table list, as the new tentative value. And this is binary search continuing in action, somewhat. It should end at the target of 5. The above loop (with its iterations) is ended. 

A new loop begins with 5 as the next binary search target value. Beginning again from index 0 with value 2 of the given array: If 5 is the minimum large sum, will it be possible to divide the given list into 3 blocks only, not necessarily of equal widths, and some may be of zero width, so that at least one of the blocks has a sum of 5, and the other sums are either 5 or below? - Well, that is to be verified, from the given list, beginning from index 0, with its value, 2. The beginning sum for the first block of this loop is 0. Is 2 greater the 5, the tentative minimum large sum? - No. So the first block sum should be 0 + 2 = 2 for given list index 0. Is the next number 1, from the given array (list) greater than 5? - No. So the first block sum should be 0 + 2 + 1 = 3 for list indexes 0 and 1. Is the next number 5, from the given array, greater than 5? - No. So the first block sum should be 0 + 2 + 1 + 5 = 8 for list indexes 0, 1, 2. Notice at this point that the running sum of the first block is greater than 5. So, instead of going to the next iteration with the next number in the given list (array), the first block has to end, for the next blocks to begin with their own running sums. The first block ends at index 1 with the sum of 3, and the second block starts at index 2 with value, 5. This is because the tentative minimum large sum is 5, and no block should have a sum above 5. The sum for the second block starts at index 2 with value, 5 and not 0. Is the next number 1 (second number of the second block), from the given array, greater than 5? - No. So the second block sum should be 5 + 1 = 6 for list indexes 2, 3. Notice at this point that the running sum of the second block is greater than 5. So, instead of going to the next iteration with the next number in the given list (array), the second block has to end, for the next blocks to begin with their own running sums. The second block ends at index 2 with the sum of 5 (just one element), and the third block starts at index 3 with value, 1. This is because the tentative minimum large sum is 5, and no block should have a sum above 5. The sum for the third block starts at index 3 with value, 1 and not 0. Is the next number 2 (of next iteration), from the given array, greater than 5? - No. So the third block sum should be 1 + 2 = 3 for list indexes 3, 4. Is the next number 2, from the given array, greater than 5? - No. So the third block sum should be 1 + 2 + 2 = 5 for list indexes 3, 4, 5. Is the next number 2, from the given array, greater than 5? - No. So the third block sum should be 1 + 2 + 2 + 2 = 7 for list indexes 3, 4, 5, 6. Notice at this point that the running sum of the third block is greater than 5. So, instead of going to the next iteration with the next number in the given list (array), the third block has to end, for the next blocks to begin with their own running sums. The third block ends at index 5 with the sum of 5, and the fourth block starts at index 6 with value, 2. This is because the tentative minimum large sum is 5, and no block should have a sum above 5. The sum for the fourth block starts at index 6 with value, 2 and not 0. Is the next number which does not exist (assumed to be 0), from the given list, after end of whole given list, greater than 5? - No. So the fourth block sum should be 2 + 0 = 2 for list index 6. There are four blocks with the distribution: [2, 1], [5], [1, 2, 2], [2] with minimal tentative large sum of 5. There are supposed to be three blocks, but it happens to be four blocks here. So, these four blocks and its binary search target value of 5, is disqualified. The previous tentative minimal large sum of 6 (previous binary search target value) is returned. In fact, the fourth block should not have been looked for. The binary search algorithm ends here in O(log₂n) time. Do not forget that the loops for the block sets, add extra time.

Strategy

A special binary search algorithm is needed. It starts with 35 as the tentative target value, which is the maximum value of all the possible block sums from the table. The other tentative target values are obtained through the special binary search algorithm. A tentative target value is assumed to be the minimal large sum. The binary search is done by a function called the solution() function. 

There is another function called the tryLargeSum() function. This function divides the given list into different sets of K (3) blocks. For each set, it determines if the largest sum is equal to or less than the tentative binary search target value, which is assumed to be the minimal large sum. If the test succeeds, the tryLargeSum() function returns true to the binary search function. If it fails, it returns false.

If the test succeeds, it does not mean that the tentative target value is the minimal (smallest) large sum. The binary search algorithm has to complete for the last (smallest) large sum to be known and accepted. 

A test will fail if one element in the given list, is greater than the tentative target (tentative minimal large sum), or with the tentative target, more than K (3) blocks are obtained. If the tentative target is greater than the sum of all the elements in the given list, then the test (tryLargeSum() function) will still return true. However, that will occur at the beginning of the binary search. As the binary search continues, there will still be a more acceptable small large sum.

The tentative target is a sum and not necessarily a given list element. So the tentative target is obtained from the table of possible block sums, and not from the given list. 

The special binary search algorithm continuously divides (lower interval limit + upper interval limit) by 2, for the tentative target, for the next test, beginning from MxN (35 = 0 + 35). The binary search will only continue in the upper (right) half of its interval, if a test fails. 

Smart Solution (same as above)

The program is repeated here for quick reading reach. The program is (read the code and comments): 

<script type='text/javascript'>
    "use strict";    

    function tryLargeSum(A, maxblockscount, mid) {
        //maxblockscount is K

        let sum=0;
        let blockscount=1;    //non-empty array A
        let size = A.length;
    
        for (let i=0; i<size; i++) {
            if (A[i]>mid)
                return false;    //not possible for one element to be greater than any largest sum.
    
            sum += A[i];
            if (sum > mid){
                blockscount++;
                if (blockscount > maxblockscount) 
                    return false;
                sum = A[i];
            }
        }
    
        if (blockscount > maxblockscount) 
            return false;
        
        return true;
    }

    function solution(K, M, A) {
        let N = A.length;
    
        let loIndex = 0;    //least blocks sum
        let hiIndex = M * N;    //maximum blocks sum
        let midIndex;
    
        let result = hiIndex;    //large sum beginning at maximum, then downwards
    
        while(loIndex <= hiIndex){
            midIndex = parseInt((loIndex + hiIndex)/2);
        
            if (tryLargeSum(A, K, midIndex)==true){
                hiIndex = midIndex - 1;
                if (midIndex < result)
                   result = midIndex;    //index and value are same
            }else{
                loIndex = midIndex + 1;
            }
        }
        return result;
    }


    let A = [2, 1, 5, 1, 2, 2, 2];

    let ret = solution(3, 5, A);

    document.write(ret + '<br>'); 

</script>

The output is: 

    6

Note that the solution() function begins by sending 17 to the tryLargeSum() function and not 35: that is not an issue. At app.codility.com/programmers the scoring and detected time complexity for this solution() is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N*log(N+M))