Last Updated: 10 Apr, 2021
One Segment
Easy
Asked in company
You are given a binary string ‘STR’, containing only zeroes and ones. This string does not contain any leading zero.
Your task is to determine if this string contains at most one contiguous segment of ones.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains the binary string ‘STR’.
Output Format:
For each test case, print “Yes” if the string contains at most one contiguous segment of ones or print “No” if it contains more than one contiguous segment.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= |STR| < 10^6
Where ‘T’ denotes the number of test cases and |STR| represents the length of the string ‘STR’
Time Limit: 1sec
Approaches
We know that the given string does not contain leading zeroes. This means that the string definitely has at least one segment of ones. For this string to contain only one segment of ones, this should be the only segment. When the first zero appears, this segment ends at that index. So, if any zero is followed by a one, then that will be the new segment. So the approach is to find whether the string contains a zero which is followed by a one or not. If it does contain such a zero, then the string has more than one segment of ones.
Algorithm:
- Define a variable, say ‘len’, to be equal to the length of the string.
- Now run a loop from 'i' = 0 to ‘i’ < len-1, and do:
- If STR[i] == 0 and STR[i+1] == 1, return False.
- If no zero is followed by a one, return True.