## Divide Chocolate

• Time:O(n\log(\Sigma |\texttt{sweetness[i]}|))
• Space:O(1)

## C++

``````class Solution {
public:
int maximizeSweetness(vector<int>& sweetness, int k) {
int l = sweetness.size() / (k + 1);
int r = accumulate(begin(sweetness), end(sweetness), 0) / (k + 1);

while (l < r) {
const int m = (l + r) / 2;
if (canEat(sweetness, k, m))
l = m + 1;
else
r = m;
}

return canEat(sweetness, k, l) ? l : l - 1;
}

// true if can eat m sweetness (min sweetness of each piece)
private:
bool canEat(const vector<int>& sweetness, int k, int m) {
int pieces = 0;
int sum = 0;  // running sum

for (const int s : sweetness) {
sum += s;
if (sum >= m) {
if (++pieces > k)
return true;
sum = 0;
}
}

return false;
};
};
``````

## JAVA

``````class Solution {
public int maximizeSweetness(int[] sweetness, int k) {
int l = sweetness.length / (k + 1);
int r = Arrays.stream(sweetness).sum() / (k + 1);

while (l < r) {
final int m = (l + r) / 2;
if (canEat(sweetness, k, m))
l = m + 1;
else
r = m;
}

return canEat(sweetness, k, l) ? l : l - 1;
}

// true if you can eat m sweetness (min sweetness of each piece)
private boolean canEat(int[] sweetness, int k, int m) {
int pieces = 0;
int sum = 0; // running sum

for (final int s : sweetness) {
sum += s;
if (sum >= m) {
if (++pieces > k)
return true;
sum = 0;
}
}

return false;
}
}
``````

## Python

``````class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
l = len(sweetness) // (k + 1)
r = sum(sweetness) // (k + 1)

# True if you can eat m sweetness (min sweetness of each piece)
def canEat(m: int) -> bool:
pieces = 0
sum = 0  # running sum

for s in sweetness:
sum += s
if sum >= m:
pieces += 1
if pieces > k:
return True
sum = 0

return False

while l < r:
m = (l + r) // 2
if canEat(m):
l = m + 1
else:
r = m

return l if canEat(l) else l - 1
``````