Last Updated: 12 Apr, 2021

String Without 000 Or 111

Easy

Asked in company

Solve now

Problem statement

You have to create any binary string ‘S’ of length ‘M+N’ which has exactly ‘M’ 0’s and ‘N’ 1’s. S can not have ‘111’ or ‘000’ as a substring.

Given ‘M’ and ‘N’ it is guaranteed that there exists at least one binary string ‘S’.

The substring of a string is obtained by deleting characters from the start and end of the string.

For example:

M = 6, N = 6
ANS = “110011001100”

In ans no three consecutive characters are same. 
ANS=”001100110011” is also a valid answer.

Input Format:

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line and the only line of each test case contain two space-separated integers ‘M’ and ‘N’.

Output Format:

For each test case print any binary string ‘S’ satisfying all the conditions.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= M+N <= 5000 

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We will iterate from left to right and check for the remaining numbers of 1’s and 0’s to be added and check if it can be added without violating the constrain.

The algorithm will be-

ANS = []
While (N + M > 0)
- If M > N
  - If ans.size() > 1 and ans[ans.size() - 1] == ans[ans.size() - 2] == ’0’
    - If last two characters are equal to ‘0’ than we can not Add ‘0’
    - ANS.append(‘1’)
    - N -= 1
  - Else
    - ANS.append(‘0’)
    - M -= 1
- Else
  - If ans.size() > 1 and ans[ans.size() - 1] == ans[ans.size() - 2] == ’1’
    - If last two characters are equal to ‘1’ than we can not Add ‘1’
    - ANS.append(‘0’)
    - M -= 1
  - Else
    - Adding the most common character
    - ANS.append(‘1’)
    - N -= 1
Return concatination_of(ANS)

Solve now