Given a binary string S of length N and an integer X, the task is to check if there exists a right wise circular rotation of the string such that every 2 adjacent 0?s are separated by at most X 1?s.
Note: The first and the last 0s in the string are not considered to be adjacent
Examples:
Input: S = “010110”, X = 1
Output: Yes
?Explanation: The 6 circular rotations of the string
S = {“010110”, “001011”, “100101”, “110010”, “011001”, “101100”}
out of which second , third and fourth strings satisfy the criteria.
Hence there exist a binary string which satisfy above condition.Input: S = “0101”, X = 0
?Output: No
An efficient approach: (No Addition of Auxiliary Space)
The input string could be thought of as a circle once we connect the last of the string to the first of it. The idea is to find out the first position of zero where the consecutive 1s between this element and the previous zero element is more than X. Next, if we need to rotate the string from that position to the left such that rest of elements in the string follows the constraints i.e. no of 1s between each pair of adjacent 0 is at most X. If we could not find any such arrangement after performing multiple rotation, then the Answer is No, else Yes. Only checking the rotation for the first incorrect position is sufficient because, there exists no right-wise circular rotation of the string such that every 2 adjacent 0?s are separated by at most X 1?s, if there is multiple positions where the no of consecutive 1s between two consecutive 0s does not follow the strategy. This would been possible if we can rotate both clock wise (right rotation) and anti-clock wise (left rotation).
Follow the below steps to implement the above idea:
- Find out the first position of zero where it violates the rule (no of consecutive 1 between each pair of 0 is at most X), also track the first 0th position (it will help if any such position exists where this given rule is not satisfied)
- If any such position of zero is found, count the no of 1s from the next position and move circularly to the first of the string until the first 0th position).
- If no of consecutive 1 found is more than X, the Answer is NO, else YES
Below is the implementation of the above approach.
C++
#include <iostream>#include <string>// Function to check if sequence existbool checkIfSequenceExist(std::string str, int x){ int i = 0; int previous_zero_position = -1; int no_of_consequtive_1 = 0; int incorrect_oth_position = -1; int first_oth_position = -1; bool exist = true; // iterate through the string while (i < str.length()) { if (str[i] == '0') { // if the element is 0, check if any // previous element=0 found if (previous_zero_position != -1) { if (no_of_consequtive_1 <= x) { no_of_consequtive_1 = 0; // valid condition } else { incorrect_oth_position = i; // violates the constraint break; } } else { first_oth_position = i; } previous_zero_position = i; // update previous_zero_position to the // latest 0th position } else if (first_oth_position != -1) { // no need to track no of 1s if // there is no element=0 found so // far no_of_consequtive_1 += 1; } i += 1; } if (incorrect_oth_position != -1) { no_of_consequtive_1 = 0; i = (incorrect_oth_position + 1) % str.length(); while (i != first_oth_position) { i = (i + 1) % str.length(); no_of_consequtive_1 += 1; } if (no_of_consequtive_1 > x) { exist = false; } } return exist;}int main(){ std::string str = "010110"; int x = 1; bool exist = checkIfSequenceExist(str, x); if (exist) { std::cout << "Yes" << std::endl; } else { std::cout << "No" << std::endl; } return 0;}// This code is contributed by shivamsharma215 |
Java
import java.io.*;public class GFG { public static void main(String[] args) { String str = "010110"; int x = 1; boolean exist = checkIfSequeneceExist(str, x); if (exist) System.out.println("Yes"); else System.out.println("No"); } private static boolean checkIfSequeneceExist(String str, int x) { int i = 0, previousZeroPosition = -1, noOfConsequtive1 = 0, incorrectOthPosition = -1, firstOthPosition = -1; boolean exist = true; while (i < str.length()) { if (str.charAt(i) == '0') { // if the element is 0, check if // any previous element=0 found if (previousZeroPosition != -1) { if (noOfConsequtive1 <= x) noOfConsequtive1 = 0; // valid condition else { incorrectOthPosition = i; // violates the constraint break; } } else { firstOthPosition = i; } previousZeroPosition = i; // update previousZeroPosition to // the latest 0th position } else if (firstOthPosition != -1) // no need to track no of 1s if // there is no element=0 found // so far noOfConsequtive1++; i++; } if (incorrectOthPosition != -1) { noOfConsequtive1 = 0; i = (incorrectOthPosition + 1) % str.length(); while (i != firstOthPosition) { i = (i + 1) % str.length(); noOfConsequtive1++; } if (noOfConsequtive1 > x) exist = false; } return exist; }} |
Python3
def checkIfSequenceExist(str, x): i = 0 previous_zero_position = -1 no_of_consequtive_1 = 0 incorrect_oth_position = -1 first_oth_position = -1 exist = True # iterate through the string while i < len(str): if str[i] == '0': # if the element is 0, check if any previous element=0 found if previous_zero_position != -1: if no_of_consequtive_1 <= x: no_of_consequtive_1 = 0 # valid condition else: incorrect_oth_position = i # violates the constraint break else: first_oth_position = i previous_zero_position = i # update previous_zero_position to the latest 0th position elif first_oth_position != -1: # no need to track no of 1s if there is no element=0 found so far no_of_consequtive_1 += 1 i += 1 if incorrect_oth_position != -1: no_of_consequtive_1 = 0 i = (incorrect_oth_position + 1) % len(str) while i != first_oth_position: i = (i + 1) % len(str) no_of_consequtive_1 += 1 if no_of_consequtive_1 > x: exist = False return exist# Driver codestr = "010110"x = 1exist = checkIfSequenceExist(str, x)if exist: print("Yes")else: print("No") |
C#
// C# code for the above approachusing System;public class GFG { static bool checkIfSequeneceExist(string str, int x) { int i = 0, previousZeroPosition = -1, noOfConsequtive1 = 0, incorrectOthPosition = -1, firstOthPosition = -1; bool exist = true; while (i < str.Length) { if (str[i] == '0') { // if the element is 0, check if // any previous element=0 found if (previousZeroPosition != -1) { if (noOfConsequtive1 <= x) noOfConsequtive1 = 0; // valid condition else { incorrectOthPosition = i; // violates the constraint break; } } else { firstOthPosition = i; } previousZeroPosition = i; // update previousZeroPosition to // the latest 0th position } else if (firstOthPosition != -1) // no need to track no of 1s if // there is no element=0 found // so far noOfConsequtive1++; i++; } if (incorrectOthPosition != -1) { noOfConsequtive1 = 0; i = (incorrectOthPosition + 1) % str.Length; while (i != firstOthPosition) { i = (i + 1) % str.Length; noOfConsequtive1++; } if (noOfConsequtive1 > x) exist = false; } return exist; } static public void Main() { // Code string str = "010110"; int x = 1; bool exist = checkIfSequeneceExist(str, x); if (exist) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by lokeshmvs21. |
Javascript
function checkIfSequeneceExist(str, x){ let i = 0, previousZeroPosition = -1, noOfConsequtive1 = 0, incorrectOthPosition = -1, firstOthPosition = -1; let exist = true; while (i < str.length) { if (str.charCodeAt(i) == '0') { // if the element is 0, check if // any previous element=0 found if (previousZeroPosition != -1) { if (noOfConsequtive1 <= x) noOfConsequtive1 = 0; // valid condition else { incorrectOthPosition = i; // violates the constraint break; } } else { firstOthPosition = i; } previousZeroPosition = i; // update previousZeroPosition to // the latest 0th position } else if (firstOthPosition != -1) // no need to track no of 1s if // there is no element=0 found // so far noOfConsequtive1++; i++; } if (incorrectOthPosition != -1) { noOfConsequtive1 = 0; i = (incorrectOthPosition + 1) % str.length; while (i != firstOthPosition) { i = (i + 1) % str.length; noOfConsequtive1++; } if (noOfConsequtive1 > x) exist = false; } return exist;} let str = "010110"; let x = 1; let exist = checkIfSequeneceExist(str, x); if (exist) document.write("Yes"); else document.write("No"); |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach: The problem can be solved based on the following observation:
Assuming the last character to be adjacent to first, we can find the number of ones between each pair of adjacent ones in a list. Now, the rotation of binary string is equivalent to deleting at most one element of this list. So if rest of the elements are up to X, then the answer is YES.
Follow the below steps to implement the above idea:
- Find the positions of all 0’s in the array.
- Find the number of 1s between any two adjacent 0s.
- If there is at most 1 such segment of contiguous 1s having length X or more then that segment can be partitioned to be in the start or last. So print “Yes”;
- Otherwise, it prints “No”.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check whether// such a rotation existsvoid check(string s, int n, int x){ vector<int> pos; for (int i = 0; i < n; i++) { if (s[i] == '0') pos.push_back(i); } int cnt = 0; for (int i = 0; i + 1 < pos.size(); i++) { if ((pos[i + 1] - pos[i] - 1) > x) cnt++; } if (!pos.empty() and n - pos.back() - 1 + pos[0] > x) cnt++; if (cnt <= 1) cout << "Yes\n"; else cout << "No\n";}// Driver Codeint main(){ string S = "010110"; int N = S.length(); int X = 1; // Function call check(S, N, X); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to check whether // such a rotation exists public static void check(String s, int n, int x) { int i = 0, previousZeroPosition=-1, noOfConsequtive1 =0, incorrectOthPosition = -1, firstOthPosition = -1; boolean exist=true; while(i< n) { if(s.charAt(i) == '0') { if(previousZeroPosition != -1) { if(noOfConsequtive1 <= x) noOfConsequtive1 = 0; else{ incorrectOthPosition = i; break; } }else { firstOthPosition = i; } previousZeroPosition = i; }else if(firstOthPosition != -1) { noOfConsequtive1++; } i++; } if(incorrectOthPosition != -1) { noOfConsequtive1 = 0; i = (incorrectOthPosition + 1)%n; while(i != firstOthPosition) { i = (i + 1)%n; noOfConsequtive1++; } if(noOfConsequtive1 > x) exist = false; } System.out.println(exist); } // Driver Code public static void main(String[] args) { String S = "010110"; int N = S.length(); int X = 1; // Function call check(S, N, X); }} |
Python3
# Python code to implement the approach# Function to check whether# such a rotation existsdef check(s, n, x): pos = [] for i in range(n): if (s[i] == '0'): pos.append(i) cnt = 0 for i in range(len(pos)-1): if ((pos[i + 1] - pos[i] - 1) > x): cnt += 1 if (len(pos) != 0 and n - pos[len(pos)-1] - 1 + pos[0] > x): cnt += 1 if (cnt <= 1): print("Yes") else: print("No")# Driver Codeif __name__ == "__main__": S = "010110" N = len(S) X = 1 # Function call check(S, N, X)# This code is contributed by Rohit Pradhan |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;public class GFG{ // Function to check whether // such a rotation exists public static void check(String s, int n, int x) { ArrayList pos = new ArrayList(); for (int i = 0; i < n; i++) { if (s[i] == '0') pos.Add(i); } int cnt = 0; for (int i = 0; i + 1 < pos.size(); i++) { if (((int)pos[i + 1] - (int)pos[i] - 1) > x) cnt++; } if (!pos.Any() && (n - pos[pos.Count - 1] - 1 + pos[0] > x)) cnt++; if (cnt <= 1) Console.WriteLine("Yes"); else Console.WriteLine("No"); } static public void Main (){ // Code String S = "010110"; int N = S.Length; int X = 1; // Function call check(S, N, X); }} |
Javascript
<script> function check(s, n, x){ let pos = []; for(let i = 0; i < n; i++){ if(s.charAt(i) == '0'){ pos.push(i); } } var cnt = 0; for(let i = 0; i + 1 < pos.length; i++){ if((pos[i + 1] - pos[i] - 1) > x){ cnt += 1; } } if((pos.length != 0) && (n - pos[(pos.length) - 1] + pos[0] > x)) { cnt += 1; } if(cnt <= 1){ document.write("Yes"); } else{ document.write("No"); } } let S = "010110"; let N = S.length; let X = 1; // Function call check(S, N, X); // This code is contributed by lokeshmvs21.</script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
