EJMAR21D - Editorial

PROBLEM LINK:

Practice
Contest 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;
}