Skip to content

3191. Minimum Operations to Make Binary Array Elements Equal to One I

You are given a binary array nums.

You can do the following operation on the array any number of times (possibly zero):

  • Choose any 3 consecutive elements from the array and flip all of them.

Flipping an element means changing its value from 0 to 1, and from 1 to 0.

Return the minimum number of operations required to make all elements in nums equal to 1. If it is impossible, return -1.

Example 1:

Input: nums = [0,1,1,1,0,0]

Output: 3

Explanation: We can do the following operations:

  • Choose the elements at indices 0, 1 and 2. The resulting array is nums = [**1**,**0**,**0**,1,0,0].
  • Choose the elements at indices 1, 2 and 3. The resulting array is nums = [1,**1**,**1**,**0**,0,0].
  • Choose the elements at indices 3, 4 and 5. The resulting array is nums = [1,1,1,**1**,**1**,**1**].

Example 2:

Input: nums = [0,1,1,1]

Output: -1

Explanation: It is impossible to make all elements equal to 1.

Constraints:

  • 3 <= nums.length <= 105
  • 0 <= nums[i] <= 1

Solution:

题意 给定一个 01 数组 nums，每次操作，你可以：

选一个 [0,n−3] 中的下标 i，把 nums[i],nums[i+1],nums[i+2] 都反转，即异或 1。 返回把 nums 全变成 1 的最小操作次数，如果无法做到则返回 −1。

思路 讨论是否需要对 i=0 执行操作：

如果 nums[0]=1，不需要操作，问题变成剩下 n−1 个数的子问题。 如果 nums[0]=0，一定要操作，问题变成剩下 n−1 个数的子问题。 接下来，讨论是否需要对 i=1 执行操作，处理方式同上。

依此类推，一直到 i=n−3 处理完后，还剩下 nums[n−2] 和 nums[n−1]，这两个数必须都等于 1，否则无法达成题目要求。

正确性 问：为什么这样做是对的？

答：

先操作 i 再操作 j（i\(\ne\)j），和先操作 j 再操作 i 的结果是一样的，所以操作顺序不影响答案。既然操作顺序无影响，我们可以从左到右操作。或者说，假设某种操作顺序是最优的，那么总是可以把这个操作顺序重排成从左到右操作。 对于同一个 i，操作两次等于没有操作，所以同一个 i 至多操作一次。注：操作 i 指的是反转 i,i+1,i+2 这三个位置。 结合上述两点，既然同一个 i 至多操作一次，那么从左到右操作的过程中，遇到 1 一定不能操作，遇到 0 一定要操作，所以从左到右的操作方式有且仅有一种。 既然操作方式是唯一的，我们只需模拟这个过程。 问：题目要求的「最少」体现在哪里？

答：对同一个 i 至多操作一次，就可以做到最少的操作次数。

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;

        int count = 0;

        for (int i = 0; i < n - 2; i++){
            if (nums[i] == 0){
                nums[i] = 1;
                nums[i + 1] = nums[i + 1] == 0 ? 1 : 0;
                nums[i + 2] = nums[i + 2] == 0 ? 1 : 0;
                count++;
            }
        }

        if (nums[n - 2] == 0 || nums[n - 1] == 0){
            return -1;
        }

        return count;
    }
}

// TC: O(nk)
// SC: O(1)