Minimum operations to equalize binary string

Math String Breadth-First Search Union-Find Ordered Set

45.3% acceptance

Feb 25, 2026

302

You are given a binary string s, and an integer k. In one operation, you must choose exactly k different indices and flip each '0' to '1' and each '1' to '0'. Return the minimum number of operations required to make all characters in the string equal to '1'. If it is not possible, return -1.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(s: String, k: i32) -> i32 {
    let n = s.len() as i32;
    let z = s.bytes().filter(|&b| b == b'0').count() as i32;

    if z == 0 { return 0; }

    // Parity: m*k ≡ z (mod 2). If k is even, m*k is always even.
    if k % 2 == 0 && z % 2 == 1 { return -1; }

    // When k == n every operation flips all characters simultaneously.
    // Only achievable if z == n (one flip makes all '1'). Mixed strings oscillate.
    if k == n {
      return if z == n { 1 } else { -1 };
    }

    // For k < n find minimum m such that:
    //   1. m*k ≡ z (mod 2)  (parity, handled below)
    //   2. Max-sum feasibility:
    //        m odd  → m*(n-k) >= n-z
    //        m even → m*(n-k) >= z
    //   3. m*k >= z  (implied by condition 2 for m >= 1 when k < n)
    let nk = n - k;
    let ceil_div = |a: i32, b: i32| (a + b - 1) / b;

    // Minimum m under parity=even constraint
    let min_even = {
      let req = ceil_div(z, nk).max(ceil_div(z, k));
      if req % 2 == 0 { req } else { req + 1 }
    };

    // Minimum m under parity=odd constraint
    let min_odd = {
      let req = ceil_div(n - z, nk).max(ceil_div(z, k));
      if req % 2 == 1 { req } else { req + 1 }
    };

    if k % 2 == 1 {
      // m must share parity with z
      if z % 2 == 0 { min_even } else { min_odd }
    } else {
      // k even and z even (odd z already excluded): m can be any parity
      min_even.min(min_odd)
    }
  }
}