Generate all Pairs of 0 and 1

CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given N pairs of Binary Numbers 0 and 1, your task is to generate all possible combinations such that for each 0 there should be a corresponding 1 in the combination not vice versa. In simple words for every 0 on the left there should be a 1 on the right.

"0011" is a valid combination as for both zeros there are two 1's present in the right.

"0110" is not a valid combination as there is a 1 for the first 0 but no 1 is present for the last 0 on its right.

See original problem statement here

For Example :

N = 1

Output : 1

Explanation :

All possible combination of pair 1 = "01", but "10" is not a valid pair as there is no valid 1 for 0 on the right of it.
N = 2

Output : 2

Explanation :

All possible combination of pair 2 = "0011", "0101" 
Notice here that for every 0 on the left there is a 1 on the right.

OBSERVATION:

  1. The problem becomes simple to understand if consider 0 as left bracket "(" and 1 as right bracket ")".

  2. Now we just need to balance these brackets in all possible ways.

  3. For N = 3, such possible combinations can be:
    ((())),
    (()()),
    (())(),
    ()(()),
    ()()()

Can we use Recursion here ?

Yes, Recursion seem to be a great option whenever we need to find different combinations.

SOLVING APPROACH:

  1. We will learn programming languages online and follow a recursive approach to solve the problem.

  2. Initialize an empty string Str = "" for keeping our resultant string.

  3. Initialize Zeros, Ones for number of zeros and ones, both set to 0 initially.

  4. Keep i = 0 for tracking on which index we are currently on, whenever we reach i = N, this implies we have processed the entire string of length N, just print the Str and return.

  5. On each recursive call, check if Zeros > Ones and Zeros is less than half of N, this implies that Zeros is more in number in the current string and also some 0‘s still remain for getting into the string, in this case, we can either add 0 or 1 to the current string Str, increment i by 1 and increment Zeros/Ones by 1 whoever added.

  6. Else if Zeros is equal to Ones, we can only add 0 to Str, increment i and Zeros by 1.

  7. Else(when all zeros are used / zeroes are in majority), we can add 1 to Str and increment Ones and i by 1.

STATE SPACE TREE:


SOLUTIONS:

[TABS_R id=916]

[forminator_quiz id=”1134″]

Space Complexity: O(N)

The space complexity can be reduced to O(N) if Global variable or Static variable is used to store the output string.

Refer Video for Quick Explaination:

Myself

Previous post Factorial Zeros
Next post Floor of a number

Leave a Reply

Your email address will not be published. Required fields are marked *