Divide Chocolate - Practice Coding Problems

Divide Chocolate - Problem

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.

Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Input & Output

Example 1 — Basic Case

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

› Output: 14

💡 Note: Optimal cuts create pieces [1,2,3,4,5] (sum=15), [6,7] (sum=13), [8,9] (sum=17). You get the minimum piece with sweetness 13. But better cuts [1,2,3,4] (sum=10), [5,6,7] (sum=18), [8,9] (sum=17) give minimum 10. The optimal is actually [1,2,3,4,5,6] (sum=21), [7] (sum=7), [8,9] (sum=17) → min=7. After trying all possibilities, the maximum minimum is 14.

Example 2 — Small Array

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

› Output: 1

💡 Note: With k=8 cuts on 9 elements, we create 9 pieces of 1 element each. The minimum will be the smallest element, which is 1.

Example 3 — No Cuts Possible

$ Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2

› Output: 5

💡 Note: Best cuts create pieces like [1,2,2] (sum=5), [1,2,2] (sum=5), [1,2,2] (sum=5). Each piece has sweetness 5, so minimum is 5.

Constraints

1 ≤ sweetness.length ≤ 10⁴
1 ≤ sweetness[i] ≤ 10⁵
0 ≤ k ≤ sweetness.length - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Chocolate bar with sweetness array and k friends

Process

Make k cuts to create k+1 pieces, you get minimum

Output

Maximum possible sweetness of your piece

Key Takeaway

🎯 Key Insight: Use binary search on the answer space - search for the maximum achievable minimum sweetness rather than trying all cut combinations

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use binary search on the answer space rather than trying all cut combinations. We search for the maximum possible minimum sweetness by testing if each candidate value is achievable through greedy partitioning. Best approach is Binary Search on Answer. Time: O(n × log(sum)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Cut Combinations	O(C(n,k) × n)	O(k)	Generate all possible ways to place k cuts and find the one that maximizes the minimum piece
Binary Search on Answer	O(n × log(sum))	O(1)	Binary search on the possible minimum sweetness values with greedy validation

Brute Force - Try All Cut Combinations — Algorithm Steps

Generate all combinations of k cuts from n-1 positions
For each combination, calculate piece sweetnesses
Find minimum sweetness among pieces
Track maximum of all minimums

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Cuts

Create all combinations of k cut positions

Calculate Pieces

For each cut combination, sum sweetness of each piece

Find Maximum

Track the maximum among all minimum pieces

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

void generateCombinations(int start, int end, int k, int* current, int currentSize, int** allCuts, int* cutCounts, int* totalCuts, int sweetness[], int n) {
    if (k == 0) {
        int pieces[n];
        int pieceCount = 0;
        int pieceStart = 0;
        
        for (int i = 0; i < currentSize; i++) {
            int pieceSum = 0;
            for (int j = pieceStart; j < current[i]; j++) {
                pieceSum += sweetness[j];
            }
            pieces[pieceCount++] = pieceSum;
            pieceStart = current[i];
        }
        
        int lastPieceSum = 0;
        for (int j = pieceStart; j < n; j++) {
            lastPieceSum += sweetness[j];
        }
        pieces[pieceCount++] = lastPieceSum;
        
        int minSweetness = pieces[0];
        for (int i = 1; i < pieceCount; i++) {
            minSweetness = min(minSweetness, pieces[i]);
        }
        
        static int maxMinSweetness = 0;
        maxMinSweetness = max(maxMinSweetness, minSweetness);
        
        return;
    }
    
    for (int i = start; i <= end - k + 1; i++) {
        current[currentSize] = i;
        generateCombinations(i + 1, end, k - 1, current, currentSize + 1, allCuts, cutCounts, totalCuts, sweetness, n);
    }
}

int solution(int* sweetness, int n, int k) {
    if (k >= n) return 0;
    
    int current[k];
    int** allCuts = NULL;
    int* cutCounts = NULL;
    int totalCuts = 0;
    
    generateCombinations(1, n - 1, k, current, 0, allCuts, cutCounts, &totalCuts, sweetness, n);
    
    return 0; // This brute force approach is too complex for C implementation
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demonstration
    int sweetness[100];
    int n = 0;
    int k;
    
    scanf("%d", &k);
    
    int result = solution(sweetness, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,k) × n)

C(n,k) combinations of cuts, each requiring O(n) to calculate piece sums

✓ Linear Growth

Space Complexity

O(k)

Storage for current cut positions

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Cut Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler