Rearrange a Binary String as Alternate X and Y Occurrences

Introduction

A binary string is a series of bytes. Unlike a character string which typically contains text data, a binary string is used to keep non-conventional data which includes pictures or images. The length of a given binary string is the number of bytes in the series or sequence. A binary string has a Coded Character Set Identifier(CCSID) of 65535.

In this article, we will discuss how to rearrange a binary string as alternate x and y occurrences along with its complexity.

Problem Statement

There is a binary string given with two numbers, x and y. And the binary string contains only 0’s and 1’s in it. Now the problem statement asks to Rearrange a binary string so that ‘0’ comes X-time, and then ‘1’ comes Y-time, and so on until one of the values, i.e., ‘0’ or ‘1’ is finished. 

Sample Examples

Suppose we have a binary string “myString,” and X and Y were given, then:

Example 1

Input

myString = “11010”
X = 1
Y = 1

Output:

01011

Example 2

Input

myString = “1011011”
X = 1
Y = 1

Output:

0101111

Approach

1. Take the user input as a binary string and the value of x and y.
2. Count the number of 0’s and 1’s in the input.
3. Now print 0 in the output screen x times and decrement the count of 0 by 1.
4. Perform the same with 1. Print 1 in the output screen y times and decrement the count of 1 by 1.
5. Repeat these two steps until either of the values counts becomes zero.
6. Suppose the value count of 0 becomes zero, then print the remaining one as per the value count left for 1.

Pseudo Code

This program will rearrange a binary string as alternate x and y occurrences.

FUNCTION rearrangeString(myString , X, Y)
{
	Set COUNT_zero = 0
	Set COUNT_one = 0
	COUNT 0’s and 1’s using loop
	end 
}
WHILE(Count of 0’s or 1’s is not 0)
{
	Run a loop X times
	{
		IF COUNT_zero is more than 0
		{
			Print “0” 
			Decrement COUNT_zero 
		}
	}
	Run a loop Y times
	{
		IF COUNT_one is more than 0
		{
			Print “1” 
			Decrement COUNT_one 
		}
	}
} 
{
	In the Main Function
	INPUT STRING myString, INTEGER X, INTEGER Y
	Send the value of myString, X, and Y in the rearrangeString function and print
	the result to the user
}

Implementation

class rearrangeBinaryString
{
    static void rearrangeString(String myString, int x, int y)
    {
        int count_zero = 0;
        int count_one = 0;
        int len = myString.length();
        for (int i = 0; i < len; i++)
        {
            if (myString.charAt(i) == '0')
                count_zero++;
            else
                count_one++;
        }
        while (count_zero > 0 || count_one > 0)
        {
            for (int j = 0; j < x && count_zero > 0; j++)
            {
                if (count_zero > 0)
                {
                    System.out.print ("0");
                    count_zero--;
                }
            }
            for (int j = 0; j < y && count_one> 0; j++)
            {
                if (count_one > 0)
                {
                    System.out.print("1");
                    count_one--;
                }
            } 
        }
        System.out.println();
    }
    public static void main (String[] args)
    {
        String myString = "11010";
        int x = 1;
        int y = 1;
        rearrangeString(myString, x, y);
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Time Complexity

The time complexity of the given problem is O(n), where n is the length of the binary string.

Space Complexity

The space complexity of the given problem is O(1), as no extra space was used.

Also see, Morris Traversal for Inorder.and Rabin Karp Algorithm

Must read decimal to binary c++