# 1231. Divide Chocolate

• Time: $O(n\log(\Sigma |\texttt{sweetness[i]}|))$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: int maximizeSweetness(vector& 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& 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; }; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 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