3191: Minimum-Operations-to-Make-Binary-Array-Elements-Equal-to-One-I
Medium
table of contents
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;
[i+1] ^= 1;
nums[i+2] ^= 1;
nums++ans;
}
for (int i = nums.size()-2; i < nums.size(); ++i) {
if (nums[i] == 0) return -1;
}
return ans;
}
};