Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudo Code
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What are binary numbers?
3.2.
What is the syntax of an array?
3.3.
Is a doubly linked list contiguous?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Rearrange a Binary String as Alternate X and Y Occurrences

Author Sagar Mishra
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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);
    }
}

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What are binary numbers?

Binary numbers are numbers that are represented in only 0’s and 1’s forms. There are also known as binary digits. You can express any decimal number in a binary number.

What is the syntax of an array?

Declaring an array is a simple task, i.e., VariableType variableName[d1, d2,..dn] where d is the dimension of the array and example of VariableType is int, float, bool, etc.

Is a doubly linked list contiguous?

The LinkedList data structure is a linear data structure in which each element is an object. LinkedList, unlike an array, does not have a contiguous memory structure. A pointer connects each element to the next.

Conclusion

We have extensively discussed how to rearrange a binary string as alternate x and y occurrences in this article. We started with introducing the binary string, problem statement, example, pseudocode, and implementation, and finally concluded with the time complexity of the algorithm.

We hope that this blog has helped you enhance your knowledge regarding how to rearrange a binary string as alternate x and y occurrences and if you would like to learn more, check out our other articles on the problems like the Largest sum of averagesDiamond TreeKth Distinct String in an Array and many more on our platform Coding Ninjas Studio.
Check out this problem - Longest String Chain

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Previous article
Repeated Substring Pattern
Next article
Minimum Repetitions of String A, to Generate String B as its Substring
Live masterclass