Skip to content

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 $\textit{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 $\textit{nums}$. The space complexity is $O(1)$.

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minOperations(nums []int) (ans int) {
    v := 0
    for _, x := range nums {
        x ^= v
        if x == 0 {
            v ^= 1
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

Comments