One Segment

Easy
0/40
Average time to solve is 10m
profile
Contributed by
68 upvotes
Asked in company
Amazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
11100
Sample Output 1:
Yes
Explanation for sample input 1:
In this test case, we can observe that the string contains only one contiguous segment of ones. This segment starts at the 0th index and ends at the 2nd index.
Sample Input 2:
1
111011
Sample Output 2:
No
Explanation for sample input 2:
In this case, the string contains two contiguous segments of ones. The first segment starts at the 0th index and ends at the 2nd index. The second segment starts at the 4th index and ends at the 5th index.
Hint

Think about how do we know when a new segment starts

Approaches (1)
Finding Starting Points of Segments

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:

 

  1. Define a variable, say ‘len’, to be equal to the length of the string.
  2. Now run a loop from 'i' = 0 to ‘i’ < len-1, and do:
    1. If STR[i] == 0 and STR[i+1] == 1, return False.
  3. If no zero is followed by a one, return True.
Time Complexity

O(N), where N is the length of the binary string.

 

We are going through the entire string and checking each character only once. This takes linear time.

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
One Segment
Full screen
Console