# Test if any round rotation of String has at most X 1s between two adjoining 0s

Given a binary string S of size N and an integer X, the duty is to verify if there exists a right-wise round rotation of the string such that each 2 adjoining 0′s are separated by at most X 1′s.

Word: The primary and the final 0s within the string should not thought-about to be adjoining

Examples:

Enter: S = “010110”, X = 1
Output: Sure
Clarification: The 6 round rotations of the string
S = {“010110”, “001011”, “100101”, “110010”, “011001”, “101100”}
out of which second , third and fourth strings fulfill the standards.
Therefore there exist a binary string which fulfill above situation.

Enter:  S = “0101”, X = 0
Output: No

Method: The issue will be solved primarily based on the next remark:

Assuming the final character to be adjoining to first, we are able to discover the variety of ones between every pair of adjoining ones in a listing. Now, the rotation of binary string is equal to deleting at most one factor of this record. So if remainder of the weather are as much as X, then the reply is YES.

Observe the beneath steps to implement the above thought:

• Discover the positions of all 0’s within the array.
• Discover the variety of 1s between any two adjoining 0s.
• If there’s at most 1 such phase of contiguous 1s having size X or extra then that phase will be partitioned to be within the begin or final. So print “Sure”;
• In any other case, it prints “No”.

Beneath is the implementation of the above method.

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `void` `verify(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.dimension(); i++) {` `        ``if` `((pos[i + 1] - pos[i] - 1) > x)` `            ``cnt++;` `    ``}` `    ``if` `(!pos.empty() and n - pos.again() - 1 + pos > x)` `        ``cnt++;` `    ``if` `(cnt <= 1)` `        ``cout << ``"Yesn"``;` `    ``else` `        ``cout << ``"Non"``;` `}` ` `  `int` `predominant()` `{` `    ``string S = ``"010110"``;` `    ``int` `N = S.size();` `    ``int` `X = 1;` ` `  `    ` `    ``verify(S, N, X);` ` `  `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Area: O(N)