We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make Binary Array Elements Equal to One I

Difficulty: Medium

Problem 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 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.

Key Insights

  • The operation allows flipping 3 consecutive elements, hence it affects the parity of the number of 0s in the array.
  • If the total number of 0s is not divisible by 3, it's impossible to make all elements equal to 1.
  • The greedy approach can be employed: flip the leftmost 0 and its two neighbors until all elements are 1 or it becomes impossible.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we utilize a greedy algorithm. We iterate through the array while looking for the first occurrence of 0. When we find a 0, we flip it along with the next two elements (if they exist). This approach continues until we reach the end of the array. If any 0s remain after processing, it's deemed impossible to convert all elements to 1.

Code Solutions

def min_operations(nums):
    operations = 0
    n = len(nums)
    
    for i in range(n - 2):
        if nums[i] == 0:
            # Flip the current and next two elements
            nums[i] = 1 - nums[i]
            nums[i + 1] = 1 - nums[i + 1]
            nums[i + 2] = 1 - nums[i + 2]
            operations += 1
            
    # Check if all elements are 1
    return operations if all(x == 1 for x in nums) else -1
← Back to All Questions