Problem of The Day: Minimum Operations to Make Binary Array Elements Equal to One I

Problem Statement

Brute Force [Accepted]

class Solution:
    def flipBit(self, nums, i):
        nums[i] = int(not nums[i])

    def minOperations(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0
        for i in range(N - 2):
            if nums[i] == 0:
                self.flipBit(nums, i)
                self.flipBit(nums, i + 1)
                self.flipBit(nums, i + 2)
                res += 1
        return res if all(nums) else -1

Editorial

Parity invariance means that the number of times a position is flipped determines its final value. If a position is flipped an odd number of times, its value changes, but if it is flipped an even number of times, it stays the same.

Approach 1: Using Deque

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        flip_queue = deque()  # Stores indices of flip operations
        count = 0  # Number of operations performed

        for i in range(len(nums)):
            # Remove expired flips (older than 3 indices)
            while flip_queue and i > flip_queue[0] + 2:
                flip_queue.popleft()

            # If the current element needs flipping
            if (nums[i] + len(flip_queue)) % 2 == 0:
                # Cannot flip a full triplet
                if i + 2 >= len(nums):
                    return -1
                count += 1
                flip_queue.append(i)

        return count

Approach 2: Sliding Window

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

            # only looking forward to the last element
            if nums[i - 2] == 0:
                count += 1
                # flip i-2 and i-1 and i
                nums[i - 2] = nums[i - 2] ^ 1
                nums[i - 1] = nums[i - 1] ^ 1
                nums[i] = nums[i] ^ 1

        if sum(nums) == len(nums):
            return count
        return -1

Approach 3: Bit Manipulation & Greedy

class Solution:
    def minOperations(self, nums):
        n = len(nums)
        count = 0
        for i in range(n - 2):
            if nums[i] == 0:
                nums[i] = 1
                nums[i + 1] = 1 if nums[i + 1] == 0 else 0
                nums[i + 2] = 1 if nums[i + 2] == 0 else 0
                count += 1

        if nums[n - 2] == 0 or nums[n - 1] == 0:
            return -1
        return count