Welcome to Subscribe On Youtube
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 indexi
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 benums = [0,0,0,1,0]
.  Choose the index
i = 0
. The resulting array will benums = [1,1,1,0,1]
.  Choose the index
i = 4
. The resulting array will benums = [1,1,1,0,0]
.  Choose the index
i = 3
. The resulting array will benums = [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 benums = [1,1,1,1]
.
Constraints:
1 <= nums.length <= 10^{5}
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; }