1231. Divide Chocolate

 一刷 07/2022

Version #1 Binary Search

Time O(NlogSum)

Space O(1)

Runtime: 6 ms, faster than 76.10% of Java online submissions for Divide Chocolate.

Memory Usage: 50.6 MB, less than 46.08% of Java online submissions for Divide Chocolate.

class Solution {

    public int maximizeSweetness(int[] sweetness, int k) {

        k++;

        // binary search for the minimum sweetness, the largest cutable sweetness is our answer

        int start = 0, end = 0;

        for (int sweet : sweetness) {

            end += sweet;

        }

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (canCut(sweetness, mid, k)) {

                start = mid;

            } else {

                end = mid - 1;

            }

        }

        if (canCut(sweetness, end, k)) {

            return end;

        }

        return start;

    }

    

    private boolean canCut(int[] sweetness, int min, int k) {

        int sum = 0;

        for (int i = 0; i < sweetness.length; i++) {

            sum += sweetness[i];

            if (sum >= min) {

                sum = 0;

                k--;

            }

        }

        return k <= 0;

    } 

}