Rearrange a binary string as alternate x and y occurrences

Table of Contents

Problem Statement

Suppose you are given a binary string, and two numbers x and y. The string consists of 0s and 1s only. The problem “Rearrange a binary string as alternate x and y occurrences” asks to rearrange the string such that the 0 comes x times ⇒ 1 comes y times ⇒ again 0 comes x times ⇒ 1 comes y times and so on till either 0s or 1s are finished. Then concatenate the remaining part of the string and print it.

Example

str = “01101”,

x = 1

y = 1

Explanation

First 0 printed x times, then 1 printed y times, then 0 x times then again 1 y times, but now 0 is left so we concat the remaining part of the string that is 1.

Algorithm for to Rearrange a binary string as alternate x and y occurrences

1. Count the total number of 0s and 1s.
2. Make a loop till the count of either of zeros or ones will be 0.
  1. Traverse in an individual loop for zeroCount, till the value x is reached and till the zeroCount will not be 0, print the 0, and decrease the value of zeroCount by 1.
  2. Traverse in an individual loop for onesCount, till the value y is reached and till the onesCount will not be 0, print the 1, and decrease the value of onesCount by 1.

Explanation

A binary string as an input we have given. That binary string consists of 0s and 1s only as the name suggests. We are also given with two values x and y. Such that we have to repeat the 0s in the output string x times and 1s in the output string “y” times consecutively. And if there is a string left then concatenate the remaining string with this output string. For this, we are going to use nothing but a simple counter for both the zeroCount and onesCount to keep the number and tracks for both zeroes and ones.

We are going to traverse the string each letter. Each letter will be either 0 or 1 in the form of a string. And we will count how many are zeroes and how many are ones present in the given string? The number of zeroes will be stored in the zeroCount and number of ones will be stored in onesCount. These two variables will hold the count of zeroes and ones even after we perform operations.

After getting the count of the total number of zeroes and ones in a string. We will start a loop with a condition that the loop will go on till the zeroCount or onesCount will be 0. In that loop, we will be traversing for a zeroCount and onesCount individually, with a condition that the loop will go on till the x value is reached in a loop. During this time we will be printing the ‘0’ and will decrease the value of zeroCount and print it x times. And after that another loop will be executed, which will print ‘1’ y times. Then keep on decreasing the value of onesCount. With this rest of the string will not be affected and we will get the desired output.

Code

C++ code to Rearrange a binary string as alternate x and y occurrences

#include<iostream>

using namespace std;

void arrangeZeroesAndOnes(string str, int x, int y)
{
    int zeroCount = 0;
    int onesCount = 0;
    int len = str.length();

    for (int i = 0; i < len; i++)
    {
        if (str[i] == '0')
            zeroCount++;
        else
            onesCount++;
    }
    while (zeroCount > 0 || onesCount > 0)
    {
        for (int j = 0; j < x && zeroCount > 0; j++)
        {
            if (zeroCount > 0)
            {
                cout << "0";
                zeroCount--;
            }
        }
        for (int j = 0; j < y && onesCount > 0; j++)
        {
            if (onesCount > 0)
            {
                cout << "1";
                onesCount--;
            }
        }
    }
}
int main()
{
    string str = "01101";
    int x = 1;
    int y = 1;
    arrangeZeroesAndOnes(str, x, y);
    return 0;
}

Java code to Rearrange a binary string as alternate x and y occurrences

class arrangeBinaryString
{
    static void arrangeZeroesAndOnes(String str, int x, int y)
    {
        int zeroCount = 0;
        int onesCount = 0;
        int len = str.length();

        for (int i = 0; i < len; i++)
        {
            if (str.charAt(i) == '0')
                zeroCount++;
            else
                onesCount++;
        }

        while (zeroCount > 0 || onesCount > 0)
        {
            for (int j = 0; j < x && zeroCount > 0; j++)
            {
                if (zeroCount > 0)
                {
                    System.out.print ("0");
                    zeroCount--;
                }
            }
            for (int j = 0; j < y && onesCount > 0; j++)
            {
                if (onesCount > 0)
                {
                    System.out.print("1");
                    onesCount--;
                }
            }
        }
        System.out.println();
    }
    public static void main (String[] args)
    {
        String str = "01101";
        int x = 1;
        int y = 1;
        arrangeZeroesAndOnes(str, x, y);

    }
}

Complexity Analysis

Time Complexity

O(n) where “n” is the length of the string. Here we ran the loop equal to the length of the string. Cause we were required to rearrange the string in a particular manner. We had to print all the characters which made it run in linear time complexity.

Space Complexity

O(1), because we are not storing the new string. We are simply printing the elements of the new string. So this operation does not cost us any space. And hence the space complexity for the algorithm itself is constant. While the whole program requires O(N) space for storing input.