dsacpp

Check if any pair of consecutive 1s can be separated by at most M 0s by circular rotation of a Binary String
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to check if any pair of
// consecutive 1s can be separated by at
// most M 0s by circular rotation of string S
void rotateString(int n, int m, string s)
{
	// Stores the indices of all 1s
	vector<int> v;

	// Store the number of pairs
	// separated by at least M 0s
	int cnt = 0;

	// Traverse the string
	for (int i = 0; i < n; i++) {

		if (s[i] == '1') {

			// Store the current index
			v.push_back(i);
		}
	}

	// Traverse the array containing indices
	for (int i = 1; i < (int)v.size(); i++) {

		// If the number of 0s > M,
		// then increment cnt by 1
		if ((v[i] - v[i - 1] - 1) > m) {

			// Increment cnt
			cnt++;
		}
	}

	// Check if at least M '0's lie between
	// the first and last occurrence of '1'
	if (v.size() >= 2
		&& (n - (v.back() - v[0]) - 1) > m) {

		// Increment cnt
		cnt++;
	}

	// If the value of cnt <= 1, then
	// rotation of string is possible
	if (cnt <= 1) {
		cout << "Yes";
	}

	// Otherwise
	else {
		cout << "No";
	}
}

// Driver Code
int main()
{
	string S = "101001";
	int M = 1;
	int N = S.size();
	rotateString(N, M, S);

	return 0;
}