# MinMaxDivision

Couldn’t solve this one ðŸ™‚ i got a partial solution but to complicated to even show you… Luckily Martin Kysel solved it elegantly, so here it goes written in Javascript.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
function solution(K, M, A) { // M is not the highes number in tests, so it wont work. we must calculate it manually // lower bound is the highest element, high bound is the sum of all elements low = A.reduce( ( acc, i ) => acc >= i ? acc : i, 0 ); high = A.reduce( ( acc, i ) => acc + i, 0 ); function blockSizeIsValid( A, K, max_block_size ){ var sum = 0, count = 0; for( var i = 0; i < A.length; i++ ){ if( sum + A[i] > max_block_size ){ sum = A[i]; count++; }else{ sum += A[i]; } if( count >= K ){ return false; } } return true; } while( low <= high ){ var mid = Math.floor( ( low + high ) / 2 ); if( blockSizeIsValid( A, K, mid) ){ high = mid - 1; }else{ low = mid + 1; } } return low; } |

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

Complexity:

expected worst-case time complexity is O(N*log(N+M));

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified