- 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.

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

#includeOutput/* 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[10] = {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; }

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.

## 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[10] = {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