Segregate 0s and 1s in an array
The given problem is to segregate the 0s and 1s in an array. Segregating means rearranging the array in such a way that all the 0s appear first, followed by all the 1s. The relative order of the 0s and 1s should be maintained during segregation.
Problem Statement
Given an array containing only 0s and 1s, we need to rearrange the elements such that all 0s are grouped together at the beginning, and all 1s are grouped together at the end, while preserving the original order of 0s and 1s.
Explanation with Example
Let's take an example array: [1, 0, 1, 0, 0, 1, 1, 0, 1]. After segregation, the array should become: [0, 0, 0, 0, 1, 1, 1, 1, 1]. All the 0s are together at the beginning, and all the 1s are together at the end.
Standard Pseudocode
segregate_element(arr, size):
zero = 0
one = 0
for zero = 0 to size:
if arr[zero] == 0:
swap_element(arr, one, zero)
one = one + 1
return arr
Algorithm Explanation
- The function
segregate_element
takes the arrayarr
and its sizesize
as input parameters. - It initializes two variables
zero
andone
to keep track of the position of the 0s and 1s, respectively. - The loop runs from
zero = 0
tosize-1
. - For each element in the array, if it is equal to 0, we swap it with the element at the
one
position and increment the value ofone
. - This effectively moves all the 0s to the left side of the array while preserving their relative order.
- After the loop completes, the array will be segregated, and we return the modified array.
Code Solution
// C Program
// segregate 0s and 1s in an array
#include <stdio.h>
//Function which is swapping two array elements of given location
void swap_element(int arr[], int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int arr[], int size)
{
int zero = 0;
int one = 0;
//Just before the modifying array elements
printf("Before Segregating zero and one \n");
display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented location value by one
one++;
}
}
//After modify array elements
printf("After Segregating zero and one \n");
display(arr, size);
printf("\n");
}
int main()
{
//Define array elements
int arr1[] = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = sizeof(arr1) / sizeof(arr1[0]);
segregate_element(arr1, size);
//Define array elements
int arr2[] = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = sizeof(arr2) / sizeof(arr2[0]);
segregate_element(arr2, size);
return 0;
}
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
/*
Java Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
void swap_element(int[] arr, int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("" + arr[i] + " ");
}
System.out.print("\n");
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int[] arr, int size)
{
int zero = 0;
int one = 0;
System.out.print("Before Segregating zero and one \n");
display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented location value by one
one++;
}
}
System.out.print("After Segregating zero and one \n");
display(arr, size);
System.out.print("\n");
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define array elements 1 and 0s elements
int[] arr1 = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = arr1.length;
obj.segregate_element(arr1, size);
//Define array elements
int[] arr2 = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = arr2.length;
obj.segregate_element(arr2, size);
}
}
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
/*
C++ Program
Segregate 0s and 1s in an array
*/
#include<iostream>
using namespace std;
class MyArray
{
public:
//Function which is swapping two array elements of given location
void swap_element(int arr[], int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "" << arr[i] << " ";
}
cout << "\n";
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int arr[], int size)
{
int zero = 0;
int one = 0;
cout << "Before Segregating zero and one \n";
this->display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
this->swap_element(arr, one, zero);
//visit to next location, incremented location value by one
one++;
}
}
cout << "After Segregating zero and one \n";
this->display(arr, size);
cout << "\n";
}
};
int main()
{
MyArray obj ;
int arr1[] = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.segregate_element(arr1, size);
int arr2[] = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = sizeof(arr2) / sizeof(arr2[0]);
obj.segregate_element(arr2, size);
return 0;
}
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
/*
C# Program
Segregate 0s and 1s in an array
*/
using System;
class MyArray
{
//Function which is swapping two array elements of given location
void swap_element(int[] arr, int i, int j)
{
//Get i location element
int temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write("" + arr[i] + " ");
}
Console.Write("\n");
}
//Function which is separating given array elements of 0s and 1s
void segregate_element(int[] arr, int size)
{
int zero = 0;
int one = 0;
Console.Write("Before Segregating zero and one \n");
display(arr, size);
for (zero = 0; zero < size; zero++)
{
if (arr[zero] == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented location value by one
one++;
}
}
Console.Write("After Segregating zero and one \n");
display(arr, size);
Console.Write("\n");
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
1,
1,
0,
1,
0,
0,
1,
1,
0,
0,
0,
0,
0,
1
};
int size = arr1.Length;
obj.segregate_element(arr1, size);
int[] arr2 = {
0,
1,
1,
0,
0,
0,
0,
1,
0,
1
};
size = arr2.Length;
obj.segregate_element(arr2, size);
}
}
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
<?php
/*
Php Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
function swap_element( & $arr, $i, $j)
{
//Get i location element
$temp = $arr[$i];
//set new values
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
//Function which is display array elements
function display( & $arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo "". $arr[$i] ." ";
}
echo "\n";
}
//Function which is separating given array elements of 0s and 1s
function segregate_element( & $arr, $size)
{
$zero = 0;
$one = 0;
echo "Before Segregating zero and one \n";
$this->display($arr, $size);
for ($zero = 0; $zero < $size; ++$zero)
{
if ($arr[$zero] == 0)
{
$this->swap_element($arr, $one, $zero);
//visit to next location, incremented location value by one
$one++;
}
}
echo "After Segregating zero and one \n";
$this->display($arr, $size);
echo "\n";
}
}
function main()
{
$obj = new MyArray();
//Define array elements 1 and 0s elements
$arr1 = array(1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1);
$size = count($arr1);
$obj->segregate_element($arr1, $size);
//Define array elements
$arr2 = array(0, 1, 1, 0, 0, 0, 0, 1, 0, 1);
$size = count($arr2);
$obj->segregate_element($arr2, $size);
}
main();
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
/*
Node Js Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
swap_element(arr, i, j)
{
//Get i location element
var temp = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("" + arr[i] + " ");
}
process.stdout.write("\n");
}
//Function which is separating given array elements of 0s and 1s
segregate_element(arr, size)
{
var zero = 0;
var one = 0;
process.stdout.write("Before Segregating zero and one \n");
this.display(arr, size);
for (zero = 0; zero < size; ++zero)
{
if (arr[zero] == 0)
{
this.swap_element(arr, one, zero);
//visit to next location, incremented location value by one
one++;
}
}
process.stdout.write("After Segregating zero and one \n");
this.display(arr, size);
process.stdout.write("\n");
}
}
function main()
{
var obj = new MyArray();
//Define array elements 1 and 0s elements
var arr1 = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1];
var size = arr1.length;
obj.segregate_element(arr1, size);
//Define array elements
var arr2 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1];
size = arr2.length;
obj.segregate_element(arr2, size);
}
main();
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
# Python 3 Program
# Segregate 0s and 1s in an array
class MyArray :
# Function which is swapping two array elements of given location
def swap_element(self, arr, i, j) :
# Get i location element
temp = arr[i]
# set new values
arr[i] = arr[j]
arr[j] = temp
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print("", arr[i] ," ", end = "")
i += 1
print("\n", end = "")
# Function which is separating given array elements of 0s and 1s
def segregate_element(self, arr, size) :
zero = 0
one = 0
print("Before Segregating zero and one \n", end = "")
self.display(arr, size)
while (zero < size) :
if (arr[zero] == 0) :
self.swap_element(arr, one, zero)
# visit to next location, incremented location value by one
one += 1
zero += 1
print("After Segregating zero and one \n", end = "")
self.display(arr, size)
print("\n", end = "")
def main() :
obj = MyArray()
# Define array elements 1 and 0s elements
arr1 = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]
size = len(arr1)
obj.segregate_element(arr1, size)
# Define array elements
arr2 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1]
size = len(arr2)
obj.segregate_element(arr2, size)
if __name__ == "__main__": main()
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
# Ruby Program
# Segregate 0s and 1s in an array
class MyArray
# Function which is swapping two array elements of given location
def swap_element(arr, i, j)
# Get i location element
temp = arr[i]
# set new values
arr[i] = arr[j]
arr[j] = temp
end
# Function which is display array elements
def display(arr, size)
i = 0
while (i < size)
print("", arr[i] ," ")
i += 1
end
print("\n")
end
# Function which is separating given array elements of 0s and 1s
def segregate_element(arr, size)
zero = 0
one = 0
print("Before Segregating zero and one \n")
self.display(arr, size)
while (zero < size)
if (arr[zero] == 0)
self.swap_element(arr, one, zero)
# visit to next location, incremented location value by one
one += 1
end
zero += 1
end
print("After Segregating zero and one \n")
self.display(arr, size)
print("\n")
end
end
def main()
obj = MyArray.new()
# Define array elements 1 and 0s elements
arr1 = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]
size = arr1.length
obj.segregate_element(arr1, size)
# Define array elements
arr2 = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1]
size = arr2.length
obj.segregate_element(arr2, size)
end
main()
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
/*
Scala Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
def swap_element(arr: Array[Int], i: Int, j: Int): Unit = {
//Get i location element
var temp: Int = arr(i);
//set new values
arr(i) = arr(j);
arr(j) = temp;
}
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("" + arr(i) + " ");
i += 1;
}
print("\n");
}
//Function which is separating given array elements of 0s and 1s
def segregate_element(arr: Array[Int], size: Int): Unit = {
var zero: Int = 0;
var one: Int = 0;
print("Before Segregating zero and one \n");
display(arr, size);
while (zero < size)
{
if (arr(zero) == 0)
{
swap_element(arr, one, zero);
//visit to next location, incremented location value by one
one += 1;
}
zero += 1;
}
print("After Segregating zero and one \n");
display(arr, size);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array elements 1 and 0s elements
var arr1: Array[Int] = Array(1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1);
var size: Int = arr1.length;
obj.segregate_element(arr1, size);
//Define array elements
var arr2: Array[Int] = Array(0, 1, 1, 0, 0, 0, 0, 1, 0, 1);
size = arr2.length;
obj.segregate_element(arr2, size);
}
}
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
/*
Swift Program
Segregate 0s and 1s in an array
*/
class MyArray
{
//Function which is swapping two array elements of given location
func swap_element(_ arr: inout[Int], _ i: Int, _ j: Int)
{
//Get i location element
let temp: Int = arr[i];
//set new values
arr[i] = arr[j];
arr[j] = temp;
}
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("", arr[i] ," ", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Function which is separating given array elements of 0s and 1s
func segregate_element(_ arr: inout[Int], _ size: Int)
{
var zero: Int = 0;
var one: Int = 0;
print("Before Segregating zero and one \n", terminator: "");
self.display(arr, size);
while (zero < size)
{
if (arr[zero] == 0)
{
self.swap_element(&arr, one, zero);
//visit to next location, incremented location value by one
one += 1;
}
zero += 1;
}
print("After Segregating zero and one \n", terminator: "");
self.display(arr, size);
print("\n", terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
//Define array elements 1 and 0s elements
var arr1: [Int] = [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1];
var size: Int = arr1.count;
obj.segregate_element(&arr1, size);
//Define array elements
var arr2: [Int] = [0, 1, 1, 0, 0, 0, 0, 1, 0, 1];
size = arr2.count;
obj.segregate_element(&arr2, size);
}
main();
Output
Before Segregating zero and one
1 1 0 1 0 0 1 1 0 0 0 0 0 1
After Segregating zero and one
0 0 0 0 0 0 0 0 1 1 1 1 1 1
Before Segregating zero and one
0 1 1 0 0 0 0 1 0 1
After Segregating zero and one
0 0 0 0 0 0 1 1 1 1
Resultant Output Explanation
Let's analyze the output for the two input arrays provided in the code:
Input 1 (arr1): [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]
Before Segregating zero and one: [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1] After Segregating zero and one: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
Input 2 (arr2): [0, 1, 1, 0, 0, 0, 0, 1, 0, 1]
Before Segregating zero and one: [0, 1, 1, 0, 0, 0, 0, 1, 0, 1] After Segregating zero and one: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
Time Complexity of the Code
The time complexity of the code is O(n) where 'n' is the size of the input array. The segregation process involves traversing the array once and performing a constant-time operation (swapping) for each element, resulting in a linear time complexity.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment