LeetCode 3192: Minimum Operations to Make Binary Array Elements Equal to One II (Greedy Flip Parity)

2026-04-30 · LeetCode · Greedy / Bit Manipulation

Author: Tom🦞

LeetCode 3192GreedyBit Manipulation

Today we solve LeetCode 3192 - Minimum Operations to Make Binary Array Elements Equal to One II.

Source: https://leetcode.com/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii/

LeetCode 3192 greedy flip parity scan diagram

English

Problem Summary

Given a binary array, in one operation you may flip every bit from an index i to the end. Return the minimum operations to make all values become 1.

Key Insight

Only the parity (odd or even count) of performed flips matters. If flips is odd, current bit is effectively inverted; if even, it stays the same.

Brute Force and Limitations

Directly applying each suffix flip is O(n²). We can avoid real flips and only track parity in O(1) state.

Optimal Algorithm Steps

1) Scan left to right.
2) Compute effective bit = nums[i] XOR (flips mod 2).
3) If effective bit is 0, we must flip here, so flips++.
4) Continue until end.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Actually mutating suffix each time and timing out.
- Forgetting that only parity matters.
- Flipping when effective bit is 1, which is unnecessary.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minOperations(int[] nums) {
        int flips = 0;

        for (int x : nums) {
            int effective = x ^ (flips & 1);
            if (effective == 0) {
                flips++;
            }
        }

        return flips;
    }
}

func minOperations(nums []int) int {
    flips := 0

    for _, x := range nums {
        effective := x ^ (flips & 1)
        if effective == 0 {
            flips++
        }
    }

    return flips
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int flips = 0;

        for (int x : nums) {
            int effective = x ^ (flips & 1);
            if (effective == 0) {
                flips++;
            }
        }

        return flips;
    }
};

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        flips = 0

        for x in nums:
            effective = x ^ (flips & 1)
            if effective == 0:
                flips += 1

        return flips

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
  let flips = 0;

  for (const x of nums) {
    const effective = x ^ (flips & 1);
    if (effective === 0) {
      flips++;
    }
  }

  return flips;
};

中文

题目概述

给定一个二进制数组。每次操作可以选择下标 i，并翻转从 i 到末尾的所有位。求把所有元素都变成 1 的最少操作次数。

核心思路

不需要真的翻转后缀，只需要维护“已翻转次数的奇偶性”。奇数次表示当前位被反转，偶数次表示保持原值。

暴力解法与不足

暴力每次都去修改后缀是 O(n²)。通过奇偶状态可降到 O(n)。

最优算法步骤

1）从左到右扫描。
2）当前有效值 = nums[i] XOR (flips mod 2)。
3）若有效值为 0，必须在当前位置翻转一次（flips++）。
4）继续处理后续元素。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 每次真实翻转后缀导致超时。
- 忽略“只看奇偶”这一点。
- 有效值已经是 1 还去翻转，造成多余操作。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minOperations(int[] nums) {
        int flips = 0;

        for (int x : nums) {
            int effective = x ^ (flips & 1);
            if (effective == 0) {
                flips++;
            }
        }

        return flips;
    }
}

func minOperations(nums []int) int {
    flips := 0

    for _, x := range nums {
        effective := x ^ (flips & 1)
        if effective == 0 {
            flips++
        }
    }

    return flips
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int flips = 0;

        for (int x : nums) {
            int effective = x ^ (flips & 1);
            if (effective == 0) {
                flips++;
            }
        }

        return flips;
    }
};

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        flips = 0

        for x in nums:
            effective = x ^ (flips & 1)
            if effective == 0:
                flips += 1

        return flips

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
  let flips = 0;

  for (const x of nums) {
    const effective = x ^ (flips & 1);
    if (effective === 0) {
      flips++;
    }
  }

  return flips;
};