## 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

- Take the user input as a binary string and the value of x and y.
- Count the number of 0’s and 1’s in the input.
- Now print 0 in the output screen x times and decrement the count of 0 by 1.
- Perform the same with 1. Print 1 in the output screen y times and decrement the count of 1 by 1.
- Repeat these two steps until either of the values counts becomes zero.
- 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);
}
}
```

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++__