Om Shree

Posted on Feb 27

💡 Beginner-Friendly Guide 'Minimum Operations to Equalize Binary String' - Problem 3666 (C++, Python, JavaScript)

#programming #cpp #python #java

In this challenge, we tackle a puzzle that feels like a digital light switch game. We need to find the most efficient way to turn all zeros into ones, but there is a catch: every move requires us to flip exactly $k$ switches at once.

Problem Summary

You're given:

A binary string $s$ consisting of '0's and '1's.
An integer $k$, representing the exact number of indices you must flip in a single operation.

Your goal:
Find the minimum number of operations required to make the entire string consist of only '1's. If it is impossible to reach this state, return -1.

Intuition

To solve this efficiently, we don't need to simulate every possible flip. Instead, we can use a mathematical approach based on the total number of zeros.

Every time we flip an index, we either change a '0' to a '1' (reducing the zero count by 1) or a '1' to a '0' (increasing the zero count by 1). If we perform $i$ operations, we have made a total of $i \times k$ flips.

Let $z$ be the initial number of zeros. After $i$ operations, for the string to be all '1's, every initial zero must have been flipped an odd number of times, and every initial one must have been flipped an even number of times. This leads to two critical conditions for a valid number of operations $i$:

Parity Match: The total number of flips $i \times k$ must have the same parity as the initial number of zeros $z$. In other words, $(i \times k - z)$ must be even.
Capacity Reach: We need enough operations to cover all zeros, but not so many that we are forced to flip ones back into zeros uncontrollably. The total flips $i \times k$ must fall within a specific range based on whether $i$ is odd or even, ensuring we can "absorb" the flips across the available characters.

Walkthrough: Understanding the Examples

Example 1: $s = "110", k = 1$

Zeros ($z$): 1, Ones ($o$): 2.
Try $i = 1$: Total flips $1 \times 1 = 1$.
Parity check: $(1 - 1)$ is 0 (even). Matches!
Range check: 1 flip is exactly what we need for 1 zero.
Result: 1

Example 2: $s = "0101", k = 3$

Zeros ($z$): 2, Ones ($o$): 2.
Try $i = 1$: Total flips $1 \times 3 = 3$. Parity $(3 - 2) = 1$ (odd). Fail.
Try $i = 2$: Total flips $2 \times 3 = 6$. Parity $(6 - 2) = 4$ (even). Matches!
Range check: With 2 operations, we can flip the two '0's once each and use the remaining 4 flips on the '1's (flipping each '1' twice, which leaves them as '1's).
Result: 2

Code Blocks

C++

class Solution {
public:
    int minOperations(string s, int k) {
        long long z = 0;
        for (char c : s) if (c == '0') ++z;
        long long n = s.length();
        long long o = n - z;

        if (z == 0) return 0;

        for (long long i = 1; i <= n; ++i) {
            long long total_flips = i * k;
            // Check if the total flips can realistically result in 0 zeros
            if ((total_flips - z) % 2 != 0) continue;

            if (i % 2 != 0) {
                if (total_flips >= z && total_flips <= (z * i + o * (i - 1))) return (int)i;
            } else {
                if (total_flips >= z && total_flips <= (z * (i - 1) + o * i)) return (int)i;
            }
        }
        return -1;
    }
};

Python

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        z = s.count('0')
        n = len(s)
        o = n - z

        if z == 0:
            return 0

        for i in range(1, n + 1):
            total_flips = i * k
            # Parity check: difference between total flips and zeros must be even
            if (total_flips - z) % 2 != 0:
                continue

            if i % 2 != 0:
                if z <= total_flips <= (z * i + o * (i - 1)):
                    return i
            else:
                if z <= total_flips <= (z * (i - 1) + o * i):
                    return i

        return -1

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var minOperations = function(s, k) {
    let z = 0;
    for (let char of s) {
        if (char === '0') z++;
    }
    const n = s.length;
    const o = n - z;

    if (z === 0) return 0;

    for (let i = 1; i <= n; i++) {
        let totalFlips = BigInt(i) * BigInt(k);
        let bigZ = BigInt(z);
        let bigO = BigInt(o);
        let bigI = BigInt(i);

        // Parity check
        if ((totalFlips - bigZ) % 2n !== 0n) continue;

        if (i % 2 !== 0) {
            if (totalFlips >= bigZ && totalFlips <= (bigZ * bigI + bigO * (bigI - 1n))) {
                return i;
            }
        } else {
            if (totalFlips >= bigZ && totalFlips <= (bigZ * (bigI - 1n) + bigO * bigI)) {
                return i;
            }
        }
    }
    return -1;
};

Key Takeaways

Parity Logic: In flip-based problems, the "odd/even" nature of operations is often more important than the operations themselves.
Counting vs. Simulating: When constraints are large ($10^5$), look for mathematical patterns in counts (zeros vs. ones) rather than trying to simulate every string state.
Boundary Conditions: Always check if the total work required ($i \times k$) can be distributed across the available "slots" ($n$ characters) without violating the goal.

Final Thoughts

This problem is a classic example of how "Hard" problems on LeetCode often require a shift from a Simulation mindset to a Mathematical mindset. In real-world software engineering, this type of logic is vital in fields like Error Correction Codes or Cryptography, where we must ensure that a sequence of bitwise operations results in a specific target state. Mastering parity and state-space constraints is a hallmark of a senior engineer.

DEV Community