Need explanation for algorithm searching minimal large sum

Question

I'm solving Codility questions as practice and couldn't answer one of the questions. I found the answer on the Internet but I don't get how this algorithm works. Could someone walk me through it step-by-step? Here is the question:

 /*
  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:
    class Solution { public int solution(int K, int M, int[] 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.
 */

And here is the solution I found with my comments about parts which I don't understand:

      public static int solution(int K, int M, int[] A) {
    int lower = max(A);  // why lower is max?
    int upper = sum(A);  // why upper is sum?
    while (true) {
      int mid = (lower + upper) / 2;
      int blocks = calculateBlockCount(A, mid); // don't I have specified number of blocks? What blocks do? Don't get that.
      if (blocks < K) {
        upper = mid - 1;
      } else if (blocks > K) {
        lower = mid + 1;
      } else {
        return upper;
      }
    }
  }

  private static int calculateBlockCount(int[] array, int maxSum) {
    int count = 0;
    int sum = array[0];
    for (int i = 1; i < array.length; i++) {
      if (sum + array[i] > maxSum) {
        count++;
        sum = array[i];
      } else {
        sum += array[i];
      }
    }
    return count;
  }

  // returns sum of all elements in an array
  private static int sum(int[] input) {
    int sum = 0;
    for (int n : input) {
      sum += n;
    }
    return sum;
  }

  // returns max value in an array
  private static int max(int[] input) {
    int max = -1;
    for (int n : input) {
      if (n > max) {
        max = n;
      }
    }
    return max;
  }

Answer 1

So what the code does is using a form of binary search (How binary search works is explained quite nicely here, https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/. It also uses an example quite similar to your problem.). Where you search for the minimum sum every block needs to contain. In the example case, you need the divide the array in 3 parts

When doing a binary search you need to define 2 boundaries, where you are certain that your answer can be found in between. Here, the lower boundary is the maximum value in the array (lower). For the example, this is 5 (this is if you divide your array in 7 blocks). The upper boundary (upper) is 15, which is the sum of all the elements in the array (this is if you divide the array in 1 block.)

Now comes the search part: In solution() you start with your bounds and mid point (10 for the example). In calculateBlockCount you count (count ++ does that) how many blocks you can make if your sum is a maximum of 10 (your middle point/ or maxSum in calculateBlockCount).
For the example 10 (in the while loop) this is 2 blocks, now the code returns this (blocks) to solution. Then it checks whether is less or more than K, which is the number of blocks you want. If its less than K your mid point is high because you're putting to many array elements in your blocks. If it's more than K, than your mid point is too high and you're putting too little array elements in your array. Now after the checking this, it halves the solution space (upper = mid-1). This happens every loop, it halves the solution space which makes it converge quite quickly.

Now you keep going through your while adjusting the mid, till this gives the amount blocks which was in your input K.

So to go though it step by step:

Mid =10 , calculateBlockCount returns 2 blocks
solution. 2 blocks < K so upper -> mid-1 =9, mid -> 7  (lower is 5)
Mid =7 , calculateBlockCount returns 2 blocks  
solution() 2 blocks < K so upper -> mid-1 =6, mid -> 5 (lower is 5, cast to int makes it 5)
Mid =5 , calculateBlockCount returns 4 blocks
solution() 4 blocks < K so lower -> mid+1 =6, mid -> 6  (lower is 6, upper is 6
Mid =6 , calculateBlockCount returns 3 blocks
So the function returns mid =6....

Hope this helps,

Gl learning to code :)

Edit. When using binary search a prerequisite is that the solution space is a monotonic function. This is true in this case as when K increases the sum is strictly decreasing.

Answer 2

Seems like your solution has some problems. I rewrote it as below:

class Solution {
public int solution(int K, int M, int[] A) {
    // write your code in Java SE 8
    int high = sum(A);
    int low = max(A);

    int mid = 0;

    int smallestSum = 0;

    while (high >= low) {
        mid = (high + low) / 2;
        int numberOfBlock = blockCount(mid, A);

        if (numberOfBlock > K) {
            low = mid + 1;
        } else if (numberOfBlock <= K) {
            smallestSum = mid;
            high = mid - 1;
        }

    }
    return smallestSum;
}

public int sum(int[] A) {
    int total = 0;
    for (int i = 0; i < A.length; i++) {
        total += A[i];
    }
    return total;
}

public int max(int[] A) {
    int max = 0;
    for (int i = 0; i < A.length; i++) {
        if (max < A[i]) max = A[i];
    }
    return max;
}

public int blockCount(int max, int[] A) {
    int current = 0;
    int count = 1;
    for (int i = 0; i< A.length; i++) {
        if (current + A[i] > max) {
            current = A[i];
            count++;
        } else {
            current += A[i];
        }
    }
    return count;
}
}

Answer 3

This is helped me in case anyone else finds it helpful.

Think of it as a function: given k (the block count) we get some largeSum.

What is the inverse of this function? It's that given largeSum we get a k. This inverse function is implemented below.

In solution() we keep plugging guesses for largeSum into the inverse function until it returns the k given in the exercise.

To speed up the guessing process, we use binary search.

public class Problem {
    int SLICE_MAX = 100 * 1000 + 1;

    public int solution(int blockCount, int maxElement, int[] array) {
        // maxGuess is determined by looking at what the max possible largeSum could be
        // this happens if all elements are m and the blockCount is 1
        // Math.max is necessary, because blockCount can exceed array.length, 
        // but this shouldn't lower maxGuess
        int maxGuess = (Math.max(array.length / blockCount, array.length)) * maxElement;
        int minGuess = 0;
        return helper(blockCount, array, minGuess, maxGuess);
    }

    private int helper(int targetBlockCount, int[] array, int minGuess, int maxGuess) {
        int guess = minGuess + (maxGuess - minGuess) / 2;
        int resultBlockCount = inverseFunction(array, guess);
        // if resultBlockCount == targetBlockCount this is not necessarily the solution
        // as there might be a lower largeSum, which also satisfies resultBlockCount == targetBlockCount
        if (resultBlockCount <= targetBlockCount) {
            if (minGuess == guess) return guess;
            // even if resultBlockCount == targetBlockCount
            // we keep searching for potential lower largeSum that also satisfies resultBlockCount == targetBlockCount
            // note that the search range below includes 'guess', as this might in fact be the lowest possible solution
            // but we need to check in case there's a lower one
            return helper(targetBlockCount, array, minGuess, guess);
        } else {
            return helper(targetBlockCount, array, guess + 1, maxGuess);
        }
    }

    // think of it as a function: given k (blockCount) we get some largeSum
    // the inverse of the above function is that given largeSum we get a k
    // in solution() we will keep guessing largeSum using binary search until 
    // we hit k given in the exercise
    int inverseFunction(int[] array, int largeSumGuess) {
        int runningSum = 0;
        int blockCount = 1;
        for (int i = 0; i < array.length; i++) {
            int current = array[i];
            if (current > largeSumGuess) return SLICE_MAX;
            if (runningSum + current <= largeSumGuess) {
                runningSum += current;
            } else {
                runningSum = current;
                blockCount++;
            }
        }
        return blockCount;
    }
}

Answer 4

From anhtuannd's code, I refactored using Java 8. It is slightly slower. Thanks anhtuannd.

IntSummaryStatistics summary = Arrays.stream(A).summaryStatistics();
    long high = summary.getSum();
    long low = summary.getMax();

    long result = 0;
    while (high >= low) {
        long mid = (high + low) / 2;
        AtomicLong blocks = new AtomicLong(1);
        Arrays.stream(A).reduce(0, (acc, val) -> {
            if (acc + val > mid) {
                blocks.incrementAndGet();
                return val;
            } else {
                return acc + val;
            }
        });
        if (blocks.get() > K) {
            low = mid + 1;
        } else if (blocks.get() <= K) {
            result = mid;
            high = mid - 1;
        }
    }
    return (int) result;

Answer 5

I wrote a 100% solution in python here. The result is here.

Remember: You are searching the set of possible answers not the array A

In the example given they are searching for possible answers. Consider [5] as 5 being the smallest max value for a block. And consider [2, 1, 5, 1, 2, 2, 2] 15 as the largest max value for a block.

Mid = (5 + 15) // 2. Slicing out blocks of 10 at a time won't create more than 3 blocks in total.

Make 10-1 the upper and try again (5+9)//2 is 7. Slicing out blocks of 7 at a time won't create more than 3 blocks in total.

Make 7-1 the upper and try again (5+6)//2 is 5. Slicing out blocks of 5 at a time will create more than 3 blocks in total.

Make 5+1 the lower and try again (6+6)//2 is 6. Slicing out blocks of 6 at a time won't create more than 3 blocks in total.

Therefore 6 is the lowest limit to impose on the sum of a block that will permit breaking into 3 blocks.