# Program to Separate 0 and 1 in an Array

• Write a program to segregate 0 and 1 in linear time complexity.
• How to separate 0 and 1 using Dutch Flag Algorithm.

Given an array of integers of size N having only 0 and 1. We have to separate 0 and 1 in an array. First group all 0's then all 1's.
For Example :
Input Array : 0 1 1 1 0 0 0 1 0 1
Output Array : 0 0 0 0 0 1 1 1 1 1

Method 1 : By Counting Number of Zero's in array.
Let inputArray be an integer array of size N having only 0 and 1.
• Using a loop, traverse inputArray from index 0 ti N-1.
• Count the number of 0's in inputArray and store it in a variable zeroCount. Hence, the number of 1's in inputArray is equal to N-zeroCount.
• Set first "zeroCount" elements to 0, and remaining elements(N - zeroCount) to 1.
Time Complexity : O(n)

## C program to separate 0 and 1 by counting 0's

```#include

/* Returns number of zero in array */
int countZero(int *array, int size){
int count = 0, i;
for(i=0; i < size; i++){
if(array[i] == 0)
count++;
}
return count;
}

/*Seperates 0 and 1 in an array.
first all 0's and then all 1's*/
void seperateOAnd1(int *array, int size){
int i, zeroCount = countZero(array, size);
/* Populate first zeroCount indexes with 0
and then remaining with 1*/
for(i = 0; i < size; i++){
if(i < zeroCount)
array[i] = 0;
else
array[i] = 1;
}
}

int main(){
int array = {0, 1, 1, 0, 0, 1, 0, 1, 0, 0};
int i;

seperateOAnd1(array, 10);

for(i = 0; i < 10; i++){
printf("%d ", array[i]);
}

return 0;
}
```
Output
```0 0 0 0 0 0 1 1 1 1
```

Method 2 : By using Dutch Flag Algorithm.
Let inputArray be an integer array of size N having only 0 and 1.
• Initialize two variables leftIndex and rightIndex to index 0 and N-1.
• Find first 1 by moving leftIndex from left to right
• Find first 0 by moving rightIndex from right to left.
• Swap array[leftIndex] and array[rightIndex].
• Repeat above process till rightIndex > leftIndex.
Time Complexity : O(n)

## C program to separate 0 and 1 by counting 0's

```#include <stdio.h>

/*Seperates 0 and 1 in an array. first all 0's and then all 1's.
This approach is similar to partition step of quick sort */
void seperateOAnd1(int *array, int size){
int temp, left = 0, right = size-1;
while(right > left){
/* traverse from left to right till we find a 1 */
while(array[left] != 1)
left++;
/* traverse from right to left till we find a 0 */
while(array[right] != 0)
right--;

if(left < right){
/* Swap array[left] and array[right] */
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
}

int main(){
int array = {0, 1, 1, 0, 0, 1, 0, 1, 0, 0};
int i;

seperateOAnd1(array, 10);

for(i = 0; i < 10; i++){
printf("%d ", array[i]);
}

return 0;
}
```
Output
```0 0 0 0 0 0 1 1 1 1
```