You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array [Basically you have to sort the array]. Traverse array only once.
Input array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Method 1 (Count 0s or 1s)
Thanks to Naveen for suggesting this method.
1) Count the number of 0s. So let’s understand with an example we have an array arr = [0, 1, 0, 1, 0, 0, 1] the size of the array is 7 now we will traverse the entire array and find out the number of zeros in the array, In this case the number of zeros is 4 so now we can easily get the number of Ones in the array by Array Length – Number Of Zeros.
2) Once we have counted, we can fill the array first we will put the zeros and then ones (we can get number of ones by using above formula).
C++
// C++ code to Segregate 0s and 1s in an array #include <bits/stdc++.h> using namespace std; // Function to segregate 0s and 1s void segregate0and1(int arr[], int n) { int count = 0; // Counts the no of zeros in arr for (int i = 0; i < n; i++) if (arr[i] == 0) count++; // Loop fills the arr with 0 until count for (int i = 0; i < count; i++) arr[i] = 0; // Loop fills remaining arr space with 1 for (int i = count; i < n; i++) arr[i] = 1; } // Function to print segregated array void print(int arr[], int n) { cout << "Array after segregation is "; for (int i = 0; i < n; i++) cout << arr[i] << " "; } // Driver function int main() { int arr[] = { 0, 1, 0, 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); segregate0and1(arr, n); print(arr, n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C code to Segregate 0s and 1s in an array #include <stdio.h> // Function to segregate 0s and 1s void segregate0and1(int arr[], int n) { int count = 0; // Counts the no of zeros in arr for (int i = 0; i < n; i++) if (arr[i] == 0) count++; // Loop fills the arr with 0 until count for (int i = 0; i < count; i++) arr[i] = 0; // Loop fills remaining arr space with 1 for (int i = count; i < n; i++) arr[i] = 1; } // Function to print segregated array void print(int arr[], int n) { printf("Array after segregation is "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); } // Driver function int main() { int arr[] = { 0, 1, 0, 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); segregate0and1(arr, n); print(arr, n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java code to Segregate 0s and 1s in an array import java.io.*; public class GFG { // function to segregate 0s and 1s static void segregate0and1(int arr[], int n) { int count = 0; // counts the no of zeros in arr for (int i = 0; i < n; i++) { if (arr[i] == 0) count++; } // loop fills the arr with 0 until count for (int i = 0; i < count; i++) arr[i] = 0; // loop fills remaining arr space with 1 for (int i = count; i < n; i++) arr[i] = 1; } // function to print segregated array static void print(int arr[], int n) { System.out.print("Array after segregation is "); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } // driver function public static void main(String[] args) { int arr[] = new int[]{ 0, 1, 0, 1, 1, 1 }; int n = arr.length; segregate0and1(arr, n); print(arr, n); } } // This code is contributed by Kamal Rawal |
Python3
# Python 3 code to Segregate # 0s and 1s in an array # Function to segregate 0s and 1s def segregate0and1(arr, n) : # Counts the no of zeros in arr count = 0 for i in range(0, n) : if (arr[i] == 0) : count = count + 1 # Loop fills the arr with 0 until count for i in range(0, count) : arr[i] = 0 # Loop fills remaining arr space with 1 for i in range(count, n) : arr[i] = 1 # Function to print segregated array def print_arr(arr , n) : print( "Array after segregation is ",end = "") for i in range(0, n) : print(arr[i] , end = " ") # Driver function arr = [ 0, 1, 0, 1, 1, 1 ] n = len(arr) segregate0and1(arr, n) print_arr(arr, n) # This code is contributed by Nikita Tiwari. |
C#
// C# code to Segregate 0s and 1s in an array using System; class GFG { // function to segregate 0s and 1s static void segregate0and1(int []arr, int n) { // counts the no of zeros in arr int count = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) count++; } // loop fills the arr with 0 until count for (int i = 0; i < count; i++) arr[i] = 0; // loop fills remaining arr space with 1 for (int i = count; i < n; i++) arr[i] = 1; } // function to print segregated array static void print(int []arr, int n) { Console.WriteLine("Array after segregation is "); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // driver function public static void Main() { int []arr = new int[]{ 0, 1, 0, 1, 1, 1 }; int n = arr.Length; segregate0and1(arr, n); print(arr, n); } } //This code is contributed by vt_m. |
PHP
<?php // PHP code to Segregate // 0s and 1s in an array // Function to segregate // 0s and 1s function segregate0and1(&$arr, $n) { $count = 0; // Counts the no // of zeros in arr for ($i = 0; $i < $n; $i++) { if ($arr[$i] == 0) $count++; } // Loop fills the arr // with 0 until count for ($i = 0; $i < $count; $i++) $arr[$i] = 0; // Loop fills remaining // arr space with 1 for ($i = $count; $i < $n; $i++) $arr[$i] = 1; } // Function to print // segregated array function toprint(&$arr , $n) { echo ("Array after segregation is "); for ($i = 0; $i < $n; $i++) echo ( $arr[$i] . " "); } // Driver Code $arr = array(0, 1, 0, 1, 1, 1 ); $n = sizeof($arr); segregate0and1($arr, $n); toprint($arr, $n); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // JavaScript code to Segregate 0s and 1s in an array // Function to segregate 0s and 1s function segregate0and1(arr, n) { let count = 0; // Counts the no of zeros in arr for (let i = 0; i < n; i++) { if (arr[i] == 0) count++; } // Loop fills the arr with 0 until count for (let i = 0; i < count; i++) arr[i] = 0; // Loop fills remaining arr space with 1 for (let i = count; i < n; i++) arr[i] = 1; } // Function to print segregated array function print(arr, n) { document.write("Array after segregation is "); for (let i = 0; i < n; i++) document.write(arr[i] + " "); } // Driver function let arr = [ 0, 1, 0, 1, 1, 1 ]; let n = arr.length; segregate0and1(arr, n); print(arr, n); // This code is contributed by Surbhi Tyagi </script> |
Output
Array after segregation is 0 0 1 1 1 1
Time Complexity : O(2n) ≅ O(n)
Auxiliary Space: O(1)
Method 1 traverses the array two times. Method 2 does the same in a single pass.
Method 1 has time complexity of O(2n) and Method 2 has time complexity of O(n)
Method 2 (Use two indexes to traverse)
Maintain two indexes. Initialize the first index left as 0 and second index right as n-1.
Do following while left < right
a) Keep incrementing index left while there are 0s at it
b) Keep decrementing index right while there are 1s at it
c) If left < right then exchange arr[left] and arr[right]
Implementation:
C++
// C++ program to sort a binary array in one pass #include <bits/stdc++.h> using namespace std; /*Function to put all 0s on left and all 1s on right*/void segregate0and1(int arr[], int size) { /* Initialize left and right indexes */ int left = 0, right = size-1; while (left < right) { /* Increment left index while we see 0 at left */ while (arr[left] == 0 && left < right) left++; /* Decrement right index while we see 1 at right */ while (arr[right] == 1 && left < right) right--; /* If left is smaller than right then there is a 1 at left and a 0 at right. Exchange arr[left] and arr[right]*/ if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } } } /* Driver code */int main() { int arr[] = {0, 1, 0, 1, 1, 1}; int i, arr_size = sizeof(arr)/sizeof(arr[0]); segregate0and1(arr, arr_size); cout << "Array after segregation "; for (i = 0; i < 6; i++) cout << arr[i] << " "; return 0; } // This is code is contributed by rathbhupendra |
C
// C program to sort a binary array in one pass #include<stdio.h> /*Function to put all 0s on left and all 1s on right*/void segregate0and1(int arr[], int size) { /* Initialize left and right indexes */ int left = 0, right = size-1; while (left < right) { /* Increment left index while we see 0 at left */ while (arr[left] == 0 && left < right) left++; /* Decrement right index while we see 1 at right */ while (arr[right] == 1 && left < right) right--; /* If left is smaller than right then there is a 1 at left and a 0 at right. Exchange arr[left] and arr[right]*/ if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } } } /* driver program to test */int main() { int arr[] = {0, 1, 0, 1, 1, 1}; int i, arr_size = sizeof(arr)/sizeof(arr[0]); segregate0and1(arr, arr_size); printf("Array after segregation "); for (i = 0; i < 6; i++) printf("%d ", arr[i]); getchar(); return 0; } |
Java
import java.io.*; public class Segregate { /*Function to put all 0s on left and all 1s on right*/ void segregate0and1(int arr[], int size) { /* Initialize left and right indexes */ int left = 0, right = size - 1; while (left < right) { /* Increment left index while we see 0 at left */ while (arr[left] == 0 && left < right) left++; /* Decrement right index while we see 1 at right */ while (arr[right] == 1 && left < right) right--; /* If left is smaller than right then there is a 1 at left and a 0 at right. Exchange arr[left] and arr[right]*/ if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } } } /* Driver Program to test above functions */ public static void main(String[] args) { Segregate seg = new Segregate(); int arr[] = new int[]{0, 1, 0, 1, 1, 1}; int i, arr_size = arr.length; seg.segregate0and1(arr, arr_size); System.out.print("Array after segregation is "); for (i = 0; i < 6; i++) System.out.print(arr[i] + " "); } } |
Python
# Python program to sort a binary array in one pass # Function to put all 0s on left and all 1s on right def segregate0and1(arr, size): # Initialize left and right indexes left, right = 0, size-1 while left < right: # Increment left index while we see 0 at left while arr[left] == 0 and left < right: left += 1 # Decrement right index while we see 1 at right while arr[right] == 1 and left < right: right -= 1 # If left is smaller than right then there is a 1 at left # and a 0 at right. Exchange arr[left] and arr[right] if left < right: arr[left] = 0 arr[right] = 1 left += 1 right -= 1 return arr # driver program to test arr = [0, 1, 0, 1, 1, 1] arr_size = len(arr) print("Array after segregation") print(segregate0and1(arr, arr_size)) # This code is contributed by Pratik Chhajer |
C#
// C# program to sort a binary array in one pass using System; class Segregate { /*Function to put all 0s on left and all 1s on right*/ void segregate0and1(int []arr, int size) { /* Initialize left and right indexes */ int left = 0, right = size - 1; while (left < right) { /* Increment left index while we see 0 at left */ while (arr[left] == 0 && left < right) left++; /* Decrement right index while we see 1 at right */ while (arr[right] == 1 && left < right) right--; /* If left is smaller than right then there is a 1 at left and a 0 at right. Exchange arr[left] and arr[right]*/ if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } } } /* Driver Program to test above functions */ public static void Main() { Segregate seg = new Segregate(); int []arr = new int[]{0, 1, 0, 1, 1, 1}; int i, arr_size = arr.Length; seg.segregate0and1(arr, arr_size); Console.WriteLine("Array after segregation is "); for (i = 0; i < 6; i++) Console.Write(arr[i] + " "); } } //This code is contributed by vt_m. |
PHP
<?php // PHP program to sort a // binary array in one pass // Function to put all 0s on // left and all 1s on right function segregate0and1(&$arr, $size) { // Initialize left and // right indexes $left = 0; $right = $size - 1; while ($left < $right) { // Increment left index // while we see 0 at left while ($arr[$left] == 0 && $left < $right) $left++; // Decrement right index // while we see 1 at right while ($arr[$right] == 1 && $left < $right) $right--; // If left is smaller than right // then there is a 1 at left // and a 0 at right. Exchange // arr[left] and arr[right] if ($left < $right) { $arr[$left] = 0; $arr[$right] = 1; $left++; $right--; } } } // Driver code $arr = array(0, 1, 0, 1, 1, 1); $arr_size = sizeof($arr); segregate0and1($arr, $arr_size); printf("Array after segregation is "); for ($i = 0; $i < 6; $i++) echo ($arr[$i]. " "); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript program to sort a binary array in one pass /*Function to put all 0s on left and all 1s on right*/function segregate0and1(arr, size) { /* Initialize left and right indexes */ let left = 0, right = size-1; while (left < right) { /* Increment left index while we see 0 at left */ while (arr[left] == 0 && left < right) left++; /* Decrement right index while we see 1 at right */ while (arr[right] == 1 && left < right) right--; /* If left is smaller than right then there is a 1 at left and a 0 at right. Exchange arr[left] and arr[right]*/ if (left < right) { arr[left] = 0; arr[right] = 1; left++; right--; } } } /* Driver code */let arr = [0, 1, 0, 1, 1, 1]; let i, arr_size = arr.length; segregate0and1(arr, arr_size); document.write("Array after segregation "); for (i = 0; i < 6; i++) document.write(arr[i] + " "); </script> |
Output
Array after segregation 0 0 1 1 1 1
Time Complexity : O(n)
Auxiliary Space: O(1)
Another approach :
1. Take two pointer type0(for element 0) starting from beginning (index = 0) and type1(for element 1) starting from end (index = array.length-1).
Initialize type0 = 0 and type1 = array.length-1
2. It is intended to Put 1 to the right side of the array. Once it is done, then 0 will definitely towards the left side of the array.
C++
// C++ program to sort a binary array in one pass #include <bits/stdc++.h> using namespace std; // Function to put all 0s on left and all 1s on right void segregate0and1(int arr[], int size) { int type0 = 0; int type1 = size - 1; while (type0 < type1) { if (arr[type0] == 1) { if (arr[type1] != 1) swap(arr[type0], arr[type1]); type1--; } else type0++; } } // Driver Code int main() { int arr[] = { 0, 1, 0, 1, 1, 1 }; int i, arr_size = sizeof(arr) / sizeof(arr[0]); segregate0and1(arr, arr_size); cout << "Array after segregation is "; for (i = 0; i < arr_size; i++) cout << arr[i] << " "; return 0; } |
C
// C program to sort a binary array in one pass #include <stdio.h> // Function to put all 0s on left and all 1s on right void segregate0and1(int arr[], int size) { int type0 = 0; int type1 = size - 1; while (type0 < type1) { if (arr[type0] == 1) { if (arr[type1] != 1) { int temp = arr[type0]; arr[type0] = arr[type1]; arr[type1] = temp; } type1--; } else type0++; } } // Driver Code int main() { int arr[] = { 0, 1, 0, 1, 1, 1 }; int i, arr_size = sizeof(arr) / sizeof(arr[0]); segregate0and1(arr, arr_size); printf("Array after segregation is "); for (i = 0; i < arr_size; i++) printf("%d ", arr[i]); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java code to segregate 0 and 1 import java.io.*; import java.util.*; class GFG { /** Method for segregation 0 and 1 given input array */ static void segregate0and1(int arr[]) { int type0 = 0; int type1 = arr.length - 1; while (type0 < type1) { if (arr[type0] == 1) { if (arr[type1] != 1) { // swap arr[type1] = arr[type1] + arr[type0]; arr[type0] = arr[type1] - arr[type0]; arr[type1] = arr[type1] - arr[type0]; } type1--; } else { type0++; } } } // Driver program public static void main(String[] args) { int[] array = { 0, 1, 0, 1, 1, 1 }; segregate0and1(array); for (int a : array) { System.out.print(a + " "); } } } |
Python3
# Python program to sort a # binary array in one pass # Function to put all 0s on # left and all 1s on right def segregate0and1(arr, size): type0 = 0 type1 = size - 1 while(type0 < type1): if(arr[type0] == 1): if(arr[type1] != 1): (arr[type0], arr[type1]) = (arr[type1], arr[type0]) type1 -= 1 else: type0 += 1 # Driver Code arr = [0, 1, 0, 1, 1, 1] arr_size = len(arr) segregate0and1(arr, arr_size) print("Array after segregation is", end = " ") for i in range(0, arr_size): print(arr[i], end = " ") # This code is contributed # by Shivi_Aggarwal |
C#
// C# code to segregate 0 and 1 using System; class GFG { // Method for segregation 0 // and 1 given input array static void segregate0and1(int[] arr) { int type0 = 0; int type1 = arr.Length - 1; while (type0 < type1) { if (arr[type0] == 1) { if (arr[type1] != 1) { // swap arr[type1] = arr[type1] + arr[type0]; arr[type0] = arr[type1] - arr[type0]; arr[type1] = arr[type1] - arr[type0]; } type1--; } else { type0++; } } } // Driver Code public static void Main(string[] args) { int[] array = new int[] { 0, 1, 0, 1, 1, 1 }; segregate0and1(array); Console.Write("Array after segregation is "); foreach(int a in array) { Console.Write(a + " "); } } } // This code is contributed by Shrikant13 |
PHP
<?php // PHP program to sort a // binary array in one pass // Function to put all 0s on // left and all 1s on right function segregate0and1(&$arr , $size) { $type0 = 0; $type1 = $size - 1; while($type0 < $type1) { if($arr[$type0] == 1) { if($arr[$type1] != 1) { $temp = $arr[$type0]; $arr[$type0] = $arr[$type1]; $arr[$type1] = $temp; } $type1--; } else $type0++; } } // Driver Code $arr = array(0, 1, 0, 1, 1, 1); $arr_size = sizeof($arr); segregate0and1($arr, $arr_size); echo ("Array after segregation is "); for ($i = 0; $i < $arr_size; $i++) echo ($arr[$i] . " "); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript program to sort a // binary array in one pass // Function to put all 0s on // left and all 1s on right function segregate0and1(arr, size) { let type0 = 0; let type1 = size - 1; while (type0 < type1) { if (arr[type0] == 1) { if (arr[type1] != 1) { // Swap arr[type1] = arr[type1] + arr[type0]; arr[type0] = arr[type1] - arr[type0]; arr[type1] = arr[type1] - arr[type0]; } type1--; } else type0++; } } // Driver Code let arr = [ 0, 1, 0, 1, 1, 1 ]; let i, arr_size = arr.length; segregate0and1(arr, arr_size); document.write("Array after segregation is "); for(i = 0; i < arr_size; i++) document.write(arr[i] + " "); // This code is contributed by subhammahato348 </script> |
Output
Array after segregation is 0 0 1 1 1 1
Time complexity: O(n)
Auxiliary Space: O(1)
// Thanks san4net for suggesting this method.
Please write comments if you find any of the above algorithms/code incorrect, or a better way to solve the same problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
