# Minimum Operations to Make Binary Array Elements Equal to One II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Naive Simulation
This approach directly simulates the process described in the problem. We iterate through the array from left to right. Whenever we encounter a `0`, we perform a flip operation starting from that index to make it a `1`. This is a greedy strategy because we fix each element from left to right, and a flip at index `i` does not affect elements before it.
**Time:** O(N^2), where N is the length of `nums`. The outer loop runs N times. In the worst case (e.g., an array of all zeros), the inner loop for flipping also runs up to N times for each outer loop iteration, resulting in a quadratic runtime. · **Space:** O(1), as we modify the input array in-place. If modifying the input is not allowed, the space complexity would be O(N) to maintain a copy of the array.
**Pros:** The logic is straightforward and directly follows the problem statement, making it easy to understand and implement.; It correctly solves the problem by making locally optimal choices that lead to a global optimum.
**Cons:** The time complexity of O(N^2) makes it too slow for large inputs, likely causing a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The core idea is to iterate through the array and fix each element one by one. When we are at index `i`, we want to ensure `nums[i]` becomes `1`. If it's already `1`, we move on. If it's `0`, the only way to change it without altering the already-fixed elements `nums[0...i-1]` is to perform an operation starting at index `i`. This operation flips all elements from `nums[i]` to the end of the array. We count this as one operation and perform the actual flip on the array. We repeat this process for all elements.

```java
class Solution {
    public int minOperations(int[] nums) {
        int operations = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // If the current element is 0, we need to flip it.
            if (nums[i] == 0) {
                operations++;
                // Simulate the flip for all elements from i to the end.
                for (int j = i; j < n; j++) {
                    nums[j] = 1 - nums[j];
                }
            }
        }
        return operations;
    }
}
```
### Algorithm
- Initialize a variable `operations` to 0.
- Iterate through the array `nums` from index `i = 0` to `n-1`.
- At each index `i`, if `nums[i]` is 0, it means we must perform a flip operation to make it 1.
- Increment `operations`.
- To simulate the flip, start another loop from `j = i` to `n-1` and change `nums[j]` to `1 - nums[j]`.
- If `nums[i]` is already 1, do nothing and continue to the next element.
- After the loop finishes, return `operations`.

## Optimized Greedy with State Tracking
This approach improves upon the naive simulation by avoiding the costly step of explicitly flipping the subarray. Instead of modifying the array, we track the cumulative effect of flips. The state of any element `nums[i]` depends on its original value and the total number of flips performed at indices `j <= i`. By maintaining a state variable that represents the parity of flips, we can determine the effective value of `nums[i]` in constant time.
**Time:** O(N), where N is the length of `nums`. We iterate through the array a single time, performing constant time operations at each step. · **Space:** O(1), as we only use a few variables (`operations`, `flipState`) to keep track of the state, regardless of the input size.
**Pros:** Extremely efficient with a linear time complexity, making it suitable for large inputs.; Optimal space complexity, using only a constant amount of extra memory.; Provides a clean and concise implementation.
**Cons:** The logic, while simple, is an abstraction of the physical process and might be slightly less intuitive to derive compared to the direct simulation.
### Explanation
The key insight is that we don't need to perform the flips. We only need to know their effect. A flip at index `j` inverts the state of all elements from `j` onwards. So, for an element at index `i`, its final state depends on its initial value and how many times it has been flipped by operations at indices `0, 1, ..., i`. We can track the parity of the number of flips with a single variable, let's call it `flipState`.

We iterate through the array. At each index `i`, we check the effective value of `nums[i]`. The effective value is `nums[i]` if an even number of flips have occurred (`flipState = 0`), and `1 - nums[i]` if an odd number of flips have occurred (`flipState = 1`). We need this effective value to be `1`. If it's `0`, we must perform a flip at index `i`. This increments our operation count and toggles the `flipState` for all subsequent elements.

```java
class Solution {
    public int minOperations(int[] nums) {
        int operations = 0;
        // Tracks the current flip state. 0 means not flipped (even flips), 1 means flipped (odd flips).
        int flipState = 0;
        for (int num : nums) {
            // If the current element's value matches the flip state, its effective value is 0.
            // For example:
            // - num=0, flipState=0 (no flip) -> effective value is 0.
            // - num=1, flipState=1 (flipped) -> effective value is 1-1=0.
            // In both cases, we need to flip.
            if (num == flipState) {
                operations++;
                // This new flip toggles the state for all subsequent elements.
                flipState = 1 - flipState;
            }
        }
        return operations;
    }
}
```
### Algorithm
- Initialize `operations = 0`.
- Initialize a state variable, `flipState = 0`. This tracks the parity of flips affecting the current element (0 for even, 1 for odd).
- Iterate through the array `nums` from `i = 0` to `n-1`.
- Determine the effective value of `nums[i]`. If `nums[i]` is the same as `flipState`, the effective value is 0.
- If the effective value is 0 (i.e., `nums[i] == flipState`), we must perform an operation.
  - Increment `operations`.
  - Toggle `flipState` (e.g., `flipState = 1 - flipState`) to reflect the new flip affecting subsequent elements.
- Return `operations`.

# Solutions
### Java

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

```

### Python

```python
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

```

### CPP

```cpp
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;
  }
};

```