645C. Enduring Exodus - Codeforces Solution C++

➤  Problem Link : 645C. Enduring Exodus 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
int n,k;

char arr[100002];
int cum[100002];

bool fun(int d)
{
	int lt,rt,li,ri;
	for(int i=1;i<=n;i++)
	{
	    if(arr[i]=='1')
	        continue;
		if(i==1)
			lt=0;
		else
		{
			li=max(1,i-d);
			lt=cum[i-1]-cum[li-1];
		}
		if(i==n)
			rt=0;
		else
		{
			ri=min(n,i+d);
			rt=cum[ri]-cum[i];
		}
		if(lt+rt>=k)
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	cum[0]=0;
	for(int i=1;i<=n;i++)
	{
		cum[i]=cum[i-1];
		if(arr[i]=='0')
			cum[i]++;
	//	cout<<cum[i]<<" ";	
	}
	int low = 1,high=n,mid;

	while(low<high)
	{
		mid=low+(high-low)/2;
		if(fun(mid))
			high=mid;
		else
			low=mid+1;
	}
	cout<<low;
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.