Divide chocolate

Array Binary Search

60.5% acceptance

Mar 31, 2026

1040

No description available.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximize_sweetness(sweetness: Vec<i32>, k: i32) -> i32 {
    let total: i32 = sweetness.iter().sum();
    let (mut lo, mut hi) = (1, total / (k + 1));
    while lo < hi {
      let mid = lo + (hi - lo + 1) / 2;
      // Can we split into k+1 pieces each with sweetness >= mid?
      let mut pieces = 0;
      let mut cur = 0;
      for &s in &sweetness {
        cur += s;
        if cur >= mid {
          pieces += 1;
          cur = 0;
        }
      }
      if pieces >= k + 1 {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo
  }
}