*828*

Question:Given an array arr[], that contains only 0’s and 1’s. Write a function that separate 0’s and 1’s in the array.

Input:0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1

Output:0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1

The objective of the problem is to segregate the array in two parts, and it is more popularly known as a variation of Dutch National Flag Problem.

#### Method 1:

- The most naive method is to count the number of elements in the given array. Let it be N.
- Do a second scan of the array and count the number of zeroes. Let it be c.
- Now fill the array with c number of 0’s and fill the remaining positions with 1.

Time Complexity:- O(2n)

#### Method 2:

We can solve this problem in a fashion similar to separating odd and even numbers in an array.

- Initialize 2 indexes, left = 0 and right = size-1.
- Increment left, till it is 0.
- Decrement right till it is 1.
- If (left < right) swap the values at arr[left] and arr[right].

void swap(int *i, int *j) { int temp = *i; *i = *j; *j = temp; } int seperateZeroAndOne(int arr[], int size) { // Initialize left and right indexes int left = 0; int right = size - 1; while(left < right) { // Increment left index till the number is 0 while(arr[left] == 0 && left < right) left++; // Decrement right index till the number is 1 while(arr[right] == 1 && left < right) right--; // Time to swap if(left < right) { swap(&arr[left], &arr[right]); left++; right--; } } }

*Time Complexity:-* O(n)