Bit Flipping to Equilibrium

Bit Flipping and Equilibrium

Theory

In digital systems, we often want to bring a binary bit array to a specific equilibrium (e.g., all 1s or all 0s) using minimum operations. If we can flip exactly k bits at a time:

• Count the number of wrong bits: w.
• The minimum number of operations required = ceil(w / k).
• If w % k ≠ 0, the last operation may include already-correct bits.

Flipping bits in a sliding window approach may require more steps, but choosing any k wrong bits at each step ensures the fewest operations.

Example 1

Initial bits: [0, 1, 1, 0]

Target equilibrium: all 1s → [1, 1, 1, 1]

k = 2 (flip 2 bits at a time)

Step 1: Count wrong bits

Wrong bits = positions 0 and 3 → total w = 2

Minimum operations = ceil(w / k) = 1 

Step 2: Flip 2 wrong bits

Operation	Bits Before	Bits Flipped	Bits After
1	[0, 1, 1, 0]	[0, 3]	[1, 1, 1, 1]

Example 2: Sliding Window

Bits: [0, 1, 0, 0, 1]

Target: all 1s → [1, 1, 1, 1, 1]

k = 2

Step 0: Initial state

0 1 0 0 1

Wrong bits = positions 0, 2, 3 → total 3

Step-by-Step Flipping

Step 1: Flip first 2 wrong bits (0 and 2)

1 1 1 0 1

Step 2: Flip remaining wrong bit (3) and one extra (1)

1 0 1 1 1

Step 3: Flip remaining wrong bit (1) and any other (0)

0 1 1 1 1

Step 4: Flip again wrong bits (0, 1)

1 1 1 1 1

Observation

• Total operations = 4 using sliding window approach.
• If you choose any k wrong bits instead of strict sliding, minimum steps = ceil(w/k) = 2.

Python Implementation

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        n = len(s)
        ts = [SortedSet() for _ in range(2)]
        for i in range(n + 1):
            ts[i % 2].add(i)
        cnt0 = s.count('0')
        ts[cnt0 % 2].remove(cnt0)
        q = deque([cnt0])
        ans = 0
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == 0:
                    return ans
                l = cur + k - 2 * min(cur, k)
                r = cur + k - 2 * max(k - n + cur, 0)
                t = ts[l % 2]
                j = t.bisect_left(l)
                while j < len(t) and t[j] <= r:
                    q.append(t[j])
                    t.remove(t[j])
            ans += 1
        return -1
s = "0101"
k = 3
sol = Solution()
print(sol.minOperations(s, k))