Table of Contents
Problem :
Given an array of 0’s and 1’s in random order , you need to separate 0’s and 1’s in an array.
For example:
|
1 2 3 4 5 |
arr[] = {0,1,0,0,1,1,1,0,1} Array after separating odd and even numbers : {0,0,0,0,1,1,1,1,1} |
Solution :
Solution 1:
- Count number of 0’s in the array. Lets say we get X 0’s
- Once we get the count, put X 0’s in the array and put (n-X) 1’s in the latter part of array.
Java code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public static int[] separate0s1sSolution1(int arr[]) { int count=0; for (int i = 0; i < arr.length; i++) { if(arr[i]==0) { count++; } } for (int i = 0; i < count; i++) { arr[i]=0; } for (int i = count; i < arr.length; i++) { arr[i]=1; } return arr; } |
Time Complexity : O(N)
Solution 2:
Algorithm:Â
Lets say array is arr[]
- Initialise two index variable , left=0 and right=arr.length-1
- Increment left variable until you get 1’s.
- Decrement right variable until you get 0’s
- If left < right, swap arr[left] and arr[right]
- In the end, you will see that you have 0’s on left side and 1’s on right side.
Java code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public static int[] separate0s1sSolution2(int arr[]) { for (int i = 0; i < arr.length; i++) { int left=0; int right=arr.length-1; while(arr[left]==0) { left++; } while(arr[right]==1) { right--; } if(left<right) { int temp=arr[left]; arr[left]=arr[right]; arr[right]=temp; } } return arr; } |
Java code to separate odd and even numbers in an array :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
package org.arpit.java2blog; public class Separate0s1sMain { public static void main(String[] args) { int arr[]={0,1,0,0,1,1,1,0,1}; System.out.println("Original Array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } arr=separate0s1sSolution1(arr); System.out.println("n==========================="); System.out.println("Solution 1"); System.out.println("nArray after separating 0's and 1's : "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println("n==========================="); System.out.println("Solution 2"); arr=separate0s1sSolution2(arr); System.out.println("nArray after separating 0's and 1's : "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } } public static int[] separate0s1sSolution1(int arr[]) { int count=0; for (int i = 0; i < arr.length; i++) { if(arr[i]==0) { count++; } } for (int i = 0; i < count; i++) { arr[i]=0; } for (int i = count; i < arr.length; i++) { arr[i]=1; } return arr; } public static int[] separate0s1sSolution2(int arr[]) { for (int i = 0; i < arr.length; i++) { int left=0; int right=arr.length-1; while(arr[left]==0) { left++; } while(arr[right]==1) { right--; } if(left<right) { int temp=arr[left]; arr[left]=arr[right]; arr[right]=temp; } } return arr; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Original Array: 0 1 0 0 1 1 1 0 1 =========================== Solution 1 Array after separating 0's and 1's : 0 0 0 0 1 1 1 1 1 =========================== Solution 2 Array after separating 0's and 1's : 0 0 0 0 1 1 1 1 1 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
package com.learn.dec.array;
public class SeperateZeroOnes {
public static void main(String[] args) {
int arr[]={0,1,0,0,1,1,1,0,1};
System.out.println(“Original Array: “);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
int l = 0 , r = arr.length – 1;
while (l arr[r]){
int temp = arr[l] ;
arr[l] = arr[r];
arr[r] = temp;
}
l++;
r–;
}
System.out.println(“\nSorted Array: “);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}