Intuition

• In this question, we find that if we flip a coin twice, then it is the same as flipping it zero times.
• Moreover, the only three ways to flip a coin is:

1. Flip this coin
2. Flip the coin before
3. Flip the coin before this coin

• This means that if we pass this coin, we can no longer flip this coin.

Approach

• In this case, we can iterate from front to end and flip every coin that is 0, and check whether the whole array is 1 at the end.
• Why is this method correct then?

First we know that we cannot flip a coin after we pass this coin.

This means that we must flip this coin. If we do not flip this coin, then this coin will remain 0, which does not satisfy the quetion. Therefore, this step is required, missing this step will not give us the array we need.

We can also prove that this will lead us to the result for every array that can achieve this step. Because you have to flip this coin no matter what operation you did.

Complexity

• Time complexity: $O(N)$, N is the length of the array.
• Space complexity: $O(1)$.

Code

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        cnt = 0
        for i in range(len(nums) - 2):
            if nums[i] == 0:
                cnt += 1
                nums[i] = 1
                nums[i + 1] = 1 - nums[i + 1]
                nums[i + 2] = 1 - nums[i + 2]

        if nums[-1] == 1 and nums[-2] == 1:
            return cnt

        return -1