Home Arrays Separate 0’s and 1’s in an array.

Separate 0’s and 1’s in an array.

by nikoo28
0 comments 2 minutes read

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

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More