Given an array of numbers consisting of only zeroes and ones, and we need to separate 0s and 1s. This problem can be solved in many ways like sorting and performing basic swapping but I learned a method to do all of this in a single iteration. So, let’s do this.
Example
Input: 1 0 1 0 0 1 0 1 1
Output: 0 0 0 0 1 1 1 1 1
Input: 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0
Output: 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
Solution Approach
Method 1
Here, we have 0s and 1s. Basically, by separating them, they would be in ascending order. So, this can also be done by using any basic sorting technique like Bubble Sort or Quick Sort. However, the time complexities can vary a lot depending on the order of the array given, and the best or worst-case complexity.
Method 2 – Optimized O(N)
Separate 0s and 1s in an array, using two pointers.
First, we take two pointers – [always] and [asuwish]. Both of them start from the beginning but the [always] pointer keeps on moving irrespective of what we get 0 or 1 but the [asuwish] pointer stops once it encounters a 1 on its way and increments only when it encounters a zero.
And the swapping occurs when,
arr[asuwish] == 1 && arr[always] == 0
I think the logic is clear, if you’re still confused take a look at the code below and perform a small dry run using pen and paper and you’ll understand it easily.
Note: The name of pointer is just to memorize easily, you can change them asuwish
Program to Separate 0s and 1s
#include <iostream>
using namespace std;
int main()
{
int arr[] = {0, 1, 1, 0, 0, 0, 1, 0};
int asuwish, always, noe, temp;
noe = sizeof(arr) / sizeof(arr[0]);
for (asuwish = 0, always = 0; always < noe; always++)
{
if (arr[asuwish] == 1 && arr[always] == 0)
{
temp = arr[always];
arr[always] = arr[asuwish];
arr[asuwish] = temp;
}
if (arr[asuwish] == 0)
asuwish++;
}
for (always = 0; always < noe; cout<<arr[always++]<<" ");
return 0;
}
Working
Here’s what happens at each iteration
0,0,1,1,0,0,1,0
0,0,0,1,1,0,1,0
0,0,0,0,1,1,1,0
0,0,0,0,0,1,1,1
Conclusion
This post [Separate 0s and 1s] is a part of my #30DaysChallenge to write a blog post every day on what I learn daily, All the Best~ Abhiram Reddy.