← Back to Index

📚 Divide Chocolate – Java Cheat Sheet

📌 What Is It?

The Divide Chocolate problem involves dividing a chocolate bar (represented as an array of sweetness levels) into k + 1 pieces such that the minimum sweetness of the piece with the least sweetness is maximized. The goal is to solve this using binary search.

🧱 Pattern Template

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int left = 1, right = 0;

        for (int sweet : sweetness) {
            right += sweet; // Total sweetness
        }

        while (left < right) {
            int mid = right - (right - left) / 2;

            if (canDivide(sweetness, k, mid)) {
                left = mid; // Try a larger minimum sweetness
            } else {
                right = mid - 1; // Try a smaller minimum sweetness
            }
        }

        return left;
    }

    private boolean canDivide(int[] sweetness, int k, int minSweetness) {
        int currentSweetness = 0, pieces = 0;

        for (int sweet : sweetness) {
            currentSweetness += sweet;

            if (currentSweetness >= minSweetness) {
                pieces++;
                currentSweetness = 0;

                if (pieces > k) {
                    return true;
                }
            }
        }

        return pieces > k;
    }
}

📊 Time Complexity

• Binary Search: O(log(S)), where S is the total sweetness.
• Validation: O(N), where N is the length of the sweetness array.
• Overall Complexity: O(N log(S)).

✅ Use Cases

• Dividing resources into groups with balanced properties
• Applications in optimization and resource allocation

📘 Common LeetCode Problems

• 1231. Divide Chocolate [Hard] Binary Search

🧪 Example: Divide Chocolate

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

Explanation:
- Divide the chocolate into [1,2,3], [4], [5], [6], [7,8,9].
- The minimum sweetness among these pieces is 6, which is maximized.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the maximum minimum sweetness.
• Edge cases: very small or very large sweetness values, or when k equals the array length.
• Precompute the total sweetness to set the binary search bounds.