Skip to content

← leetcode

Minimum Operations to Make Binary Array Elements Equal to One I

· Medium

LeetCode problem 3191

You can just use a Greedy Approach for this question.

Basically, realise that for nums[0], the only way to flip it to 1, if it was originally equal to 0, is if you flip the bits present at nums[0], nums[1] and nums[2]. Then, for all operations going forward, we can basically ignore nums[0] since we know it is already set to 1 (and there is no reason to do 2 operations on the same index as the 2nd operation reverses the 1st operation).

We can continue this train-of-thought through the entire array, until we reach the last 2 elements. If these elements are both 1, then we have successfully made all elements in nums equal to 1, and can simply return a count of all the operations made. Otherwise, it means it is impossible to make all elements in nums equal to 1, and we can simply return -1.

code

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

        for (int i = nums.size()-2; i < nums.size(); ++i) {
            if (nums[i] == 0) return -1;
        }
        return ans;
    }
};

complexity

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

time taken

  • 6 minutes and 0.75 seconds
    • literally one-shot this question