# Minimum Operations to Make Binary Array Elements Equal to One I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Queue
---
## 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** 3 **consecutive** elements from the array and **flip** **all** of them.

**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\. If it is impossible, return -1.

**Example 1:**

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

**Output:** 3

**Explanation:**  
We can do the following operations:

* Choose the elements at indices 0, 1 and 2\. The resulting array is `nums = [**1**,**0**,**0**,1,0,0]`.
* Choose the elements at indices 1, 2 and 3\. The resulting array is `nums = [1,**1**,**1**,**0**,0,0]`.
* Choose the elements at indices 3, 4 and 5\. The resulting array is `nums = [1,1,1,**1**,**1**,**1**]`.

**Example 2:**

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

**Output:** \-1

**Explanation:**  
It is impossible to make all elements equal to 1.

**Constraints:**

* `3 <= nums.length <= 105`
* `0 <= nums[i] <= 1`

# Approaches
## Greedy Approach with Auxiliary Space
This approach uses a greedy strategy. We iterate through the array from left to right, deciding at each step whether a flip is necessary. To avoid modifying the original array, we use an auxiliary array to keep track of where flips have occurred. This allows us to calculate the true state of each element on the fly.
**Time:** O(N) - We iterate through the array once. · **Space:** O(N) - We use an auxiliary array `flipMarkers` of the same size as the input array.
**Pros:** The logic is a clear simulation of the flip process.; It does not modify the original input array.
**Cons:** Requires O(N) extra space for the `flipMarkers` array, which is less efficient than constant space solutions.
### Explanation
The core idea is to simulate the process without altering the input `nums` array. We maintain a running count of `activeFlips` that affect the current element `nums[i]`. An auxiliary array, `flipMarkers`, stores whether we decided to initiate a flip at any given index. When we are at index `i`, we first check if a flip that started at `i-3` has now expired and adjust our `activeFlips` count accordingly. Then, we calculate the effective value of `nums[i]` by considering its original value and the `activeFlips`. If the effective value is 0, we are forced to perform a flip (if possible), incrementing our operation count and updating `activeFlips` and `flipMarkers`. If at any point we need to flip but cannot (i.e., we are too close to the end of the array), we conclude it's impossible.

```java
public int minOperations(int[] nums) {
    int n = nums.length;
    int operations = 0;
    int[] flipMarkers = new int[n]; // 1 if a flip starts here, 0 otherwise
    int activeFlips = 0;

    for (int i = 0; i < n; i++) {
        if (i >= 3) {
            activeFlips -= flipMarkers[i - 3];
        }

        int currentValue = (nums[i] + activeFlips) % 2;

        if (currentValue == 0) {
            if (i > n - 3) {
                return -1; // Cannot flip to make this element 1
            }
            operations++;
            activeFlips++;
            flipMarkers[i] = 1;
        }
    }
    return operations;
}
```
### Algorithm
1. Initialize `operations = 0`, an integer array `flipMarkers` of size `n` to all zeros, and `activeFlips = 0`.
2. Iterate through the array from `i = 0` to `n-1`.
3. At each index `i`, if `i >= 3`, it means a flip that started at `i-3` has just ended its effect. We update `activeFlips` by subtracting `flipMarkers[i-3]`.
4. Determine the current effective value of the element at `i`. This is `(nums[i] + activeFlips) % 2`. The `activeFlips` variable tells us how many times the current element has been flipped by operations started at `i-1` and `i-2`.
5. If the effective value is `0`, we must perform a flip. 
   - First, check if a flip is possible. A flip must involve 3 consecutive elements, so we can only start a flip if `i <= n-3`. If `i > n-3` and we need to flip, it's impossible, so return -1.
   - If possible, increment `operations`, increment `activeFlips` to account for the new flip, and mark `flipMarkers[i] = 1` to record that a flip started at `i`.
6. If the effective value is `1`, the element is already correct, so we do nothing.
7. After the loop completes, return the total `operations`.

## Greedy Approach with In-place Modification
This is the most efficient and straightforward approach. It relies on a greedy strategy where we iterate through the array and fix each element from left to right. By modifying the array in-place, we achieve an optimal solution with constant extra space.
**Time:** O(N) - We iterate through the array a single time. · **Space:** O(1) - We only use a few variables to store the count of operations and the loop index, modifying the array in-place.
**Pros:** Extremely space-efficient, using only O(1) extra space.; The logic is simple and easy to implement.; Guaranteed to find the minimum number of operations if a solution exists.
**Cons:** This approach modifies the input array, which might not be permissible in some scenarios.
### Explanation
The key insight is that for any element `nums[i]`, the decision to flip the triplet starting at `i` is determined solely by the current value of `nums[i]`. If we encounter a `0` at `nums[i]`, we must flip the subarray `[i, i+1, i+2]`. If we don't, `nums[i]` will remain `0` because any future flips will start at an index greater than `i` and won't affect it. This greedy choice at each step ensures that we are always making a necessary move. We iterate up to the `n-3`-th element, making these forced moves. After this loop, the first `n-2` elements are fixed to `1`. The final state of the last two elements determines if a solution is possible. If they are also `1`, we have found the minimum number of operations. If not, no solution exists.

```java
public int minOperations(int[] nums) {
    int n = nums.length;
    int operations = 0;

    for (int i = 0; i <= n - 3; i++) {
        if (nums[i] == 0) {
            // We must perform a flip starting at i.
            operations++;
            // Flip the three consecutive elements.
            nums[i] = 1;
            nums[i + 1] = 1 - nums[i + 1];
            nums[i + 2] = 1 - nums[i + 2];
        }
    }

    // After the loop, check if the last two elements are 1.
    // nums[0...n-3] are guaranteed to be 1 by the loop logic.
    if (nums[n - 2] == 0 || nums[n - 1] == 0) {
        return -1;
    }

    return operations;
}
```
### Algorithm
1. Initialize `operations = 0`.
2. Iterate through the array with an index `i` from `0` to `n-3`.
3. At each index `i`, check the value of `nums[i]`. Since we process from left to right, any operation starting before `i` has already been performed and `nums[i]` reflects its current state.
4. If `nums[i]` is `0`, we must perform a flip operation starting at `i`. This is our only and last chance to make `nums[i]` a `1`.
5. To perform the flip, increment `operations` and toggle the values of `nums[i]`, `nums[i+1]`, and `nums[i+2]`. (Note: flipping `nums[i]` is not strictly necessary as we won't visit it again, but it helps in visualizing the final state).
6. After the loop, the elements `nums[0]` through `nums[n-3]` are guaranteed to be `1`.
7. The last two elements, `nums[n-2]` and `nums[n-1]`, have had their final values determined by the preceding flips. We must check if they are both `1`.
8. If `nums[n-2] == 0` or `nums[n-1] == 0`, it's impossible to make the array all ones, so return `-1`.
9. Otherwise, the array is all ones, and we return the total `operations`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums) {
    int ans = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      if (nums[i] == 0) {
        if (i + 2 >= n) {
          return -1;
        }
        nums[i + 1] ^= 1;
        nums[i + 2] ^= 1;
        ++ans;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int]) -> int: ans = 0 for i, x in enumerate(nums): if x == 0: if i + 2 >= len(nums): return - 1 nums[i + 1] ^= 1 nums[i + 2] ^= 1 ans += 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums) {
    int ans = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      if (nums[i] == 0) {
        if (i + 2 >= n) {
          return -1;
        }
        nums[i + 1] ^= 1;
        nums[i + 2] ^= 1;
        ++ans;
      }
    }
    return ans;
  }
};

```