PROBLEM LINK:
Author: Anjali Jha
Tester: Akash Kumar Bhagat
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
There is a list of N integers and the integers are binary. An integer K has been given to find out if exactly K zeroes can be flipped to 1. The flipped integer should be such that its adjacent integers must not be 1.
EXPLANATION:
A loop is run from i=0 to N-1 and checked if the current and adjacent cells are 0. If yes, then the current 0 is flipped to 1, changing the original array, and K is decremented. Edge cases such as i=0 and i=N-1 need to be handled. The answer is YES if K<= 0 else NO.
TIME COMPLEXITY:
The time complexity will be O(N)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve() {
int n,k,I;
cin>>n>>k;
vector<int> a(n);
for(i=0;i<n;i++)
cin>>a[i];
if(k==0) {
cout<<"YES"<<endl;
return;
}
for (i=0;i<n;i++) {
if (!a[i] && (i == 0 || !a[i - 1]) && (i == a.size() - 1 || !a[i + 1])) {
a[i] = 1;
k--;
if(k==0)
break;
}
}
if(k==0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
int main(){
int t;
cin>>t;
while(t--)
solve();
return 0;
}