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

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

by nikoo28
0 comment

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)

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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