Divide array A into K blocks and minimize the largest sum of any block

Question

I am trying to solve a Codility problem provided.

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 A1 = 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:

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

My solution is provided below.

public static int solution(int K, int M, int[] A) {

    int N = A.length;

    int min = M;
    int sum = 0;

    for (int i = 0; i < N; i++) {
        sum += A[i];
    }

    int result = 0;

    while (min <= sum) {

        int middle = (min + sum) / 2;

        if (isVerified(A, middle, K)) {

            result = middle;
            sum = middle - 1;
        }

        //
        else {
            min = middle + 1;
        }
    }

    return result;
}


private static boolean isVerified(int[] A, int middle, int K) {

    int count = 1;
    int N = A.length;

    int sum = 0;

    for (int i = 0; i < N; i++) {

        if (sum + A[i] <= middle) {
            sum += A[i];
        }

        //
        else {
            count++;
            sum = A[i];

            if (count > K) {
                return false;
            }
        }
    }

    return true;
}

I received the 41% score from the Codility.

How do I improve the correctness of the solution?

NOTE

This question is different than the How to partition an array of integers in a way that minimizes the maximum of the sum of each partition. This question is concern about only a section and not all of them.

Why would you not link to the resource instead of have each of us hunt it down? — tripleee, Sep 03 '19 at 12:42
@Arefe I want to submit my solution and see if it will reach more than 41% score. — xiaokang, Sep 03 '19 at 12:42
@tripleee because a question was was banned earlier. Anyway, I provided it here: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/ — Arefe, Sep 03 '19 at 13:09
I think the solution is incorrect because of this line: `int min = M;`. The answer might be smaller than M -- I'd try setting `min = 0`. — danbanica, Sep 03 '19 at 17:55

Divide array A into K blocks and minimize the largest sum of any block

0 Answers0