README_EN.md

comments	difficulty	edit_url	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3192.Minimum%20Operations%20to%20Make%20Binary%20Array%20Elements%20Equal%20to%20One%20II/README_EN.md	Greedy Array Dynamic Programming

3192. Minimum Operations to Make Binary Array Elements Equal to One II

中文文档

Description

You are given a binary array nums.

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

• Choose any index i from the array and flip all the elements from index i to the end of the array.

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.

 

Example 1:

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

Output: 4

Explanation:
We can do the following operations:

• Choose the index i = 1. The resulting array will be nums = [0,0,0,1,0].
• Choose the index i = 0. The resulting array will be nums = [1,1,1,0,1].
• Choose the index i = 4. The resulting array will be nums = [1,1,1,0,0].
• Choose the index i = 3. The resulting array will be nums = [1,1,1,1,1].

Example 2:

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

Output: 1

Explanation:
We can do the following operation:

• Choose the index i = 1. The resulting array will be nums = [1,1,1,1].

 

Constraints:

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

Solutions

Solution 1: Bit Manipulation

We notice that whenever we change an element at a certain position to 1, all the elements to its right are flipped. Therefore, we can use a variable $v$ to record whether the current position and all elements to its right have been flipped. If flipped, the value of $v$ is 1, otherwise, it is 0.

We iterate through the array $\text{nums}$. For each element $x$, we perform an XOR operation between $x$ and $v$. If $x$ is 0, then we need to change $x$ to 1, which requires a flip operation. We increment the answer by one and flip the value of $v$.

After the iteration, we can obtain the minimum number of operations.

The time complexity is $O(n)$, where $n$ is the length of the array $\text{nums}$. The space complexity is $O(1)$.

Python3

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = v = 0
        for x in nums:
            x ^= v
            if x == 0:
                ans += 1
                v ^= 1
        return ans

Java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0, v = 0;
        for (int x : nums) {
            x ^= v;
            if (x == 0) {
                v ^= 1;
                ++ans;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0, v = 0;
        for (int x : nums) {
            x ^= v;
            if (x == 0) {
                v ^= 1;
                ++ans;
            }
        }
        return ans;
    }
};

Go

func minOperations(nums []int) (ans int) {
	v := 0
	for _, x := range nums {
		x ^= v
		if x == 0 {
			v ^= 1
			ans++
		}
	}
	return
}

TypeScript

function minOperations(nums: number[]): number {
    let [ans, v] = [0, 0];
    for (let x of nums) {
        x ^= v;
        if (x === 0) {
            v ^= 1;
            ++ans;
        }
    }
    return ans;
}