# 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)$.

• 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;
}
}

• 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;
}
};

• 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


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

• 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;
}