LIGHTZ - Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

Given an array of length N having values 0/1. Initially, no two 1's are adjacent. Find if it is possible to add K number of 1's such that no two 1's are adjacent.

QUICK EXPLANATION:

Find the maximum number of 1's that we can put without violating the rule. If this count is more than K then answer if 1 and 0 otherwise.

EXPLANATION:

We can find out the maximum number of 1's we can put. To do so, we can traverse over all the elements of the slots and find out those elements which are 0(implying an empty position). For every such element, we check if its both adjacent positions are also empty. If so, we can put a 1 at the current position without violating the no-adjacent-1-rule. For the first and last elements, we need not check the previous and the next adjacent positions respectively.

If the count obtained is greater than or equal to K, the required number of 1's can be put, otherwise not.

COMPLEXITIES

Here N is the size of slots.

TIme Complexity:
O(N).
We are just traversing the array from left to right.

Space Complexity:
O(1)
We don’t need any extra space, we just need to traverse the array.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

bool solve(vector<int>& f, int n) 
{
int i,cnt=0,m = f.size();

for(i=0;i<m;i++)
{
	if(f[i]==0)
	{
		if((i==0 || f[i-1]==0) && (i==m-1 || f[i+1]==0))
		{
			f[i]=1;
			cnt++;
		}
	}
}

return cnt>=n;
}

int main() {
ios_base::sync_with_stdio(false);
int t,n,k,i,x;

cin>>t;

while(t--)
{
	vector<int> v;

	cin>>n>>k;
	for(i=0;i<n;i++)
	{
		cin>>x;
		v.push_back(x);
	}

	cout<<solve(v, k)<<endl;
}

return 0;
}
1 Like