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 71 |
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; } } |
when you run above program, you will get below output:
|
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 |
