Segregate 0’s and 1 ‘s in array.
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
Readers are requested to submit their codes in comment section below. The best codes will be published on the website.
Method:–
1.Initialize two variables leftIndex and rightIndex to index 0 and N-1.
2.Find first 1 by moving leftIndex from left to right
3.Find first 0 by moving rightIndex from right to left.
4.Swap array[leftIndex] and array[rightIndex].
Repeat above process till rightIndex > leftIndex.
The time complexity for this approach is O(n).
code
[code language=”cpp”]
#include <iostream>
using namespace std;
void swap( int *a ,int *b)
{
int temp=*a;*a=*b;*b=temp;
}
int main() {
// your code goes here
int i, n,low,high;
cin>>n;int arr[n];
for(i=0;i<n;i++)
cin>>arr[i];
low=0;high=n-1;
while(low<high)
{
if(arr[low]==0 && low<high) low++;
if(arr[high]==1 && low<high) high–;
else
{
if(low<high){
swap(&arr[low],&arr[high]);
low++;
high–;}
}
for(i=0;i<n;i++)
cout<<arr[i]<<endl;
cout<<endl;
return 0;
}
[/code]
Login/Signup to comment
#include
using namespace std;
int main()
{
int n;
printf(“enter the no. of elements”);
scanf(“%d”,&n);
int a[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
#include
using namespace std;
int main()
{
int n;
printf(“enter the no. of elements”);
scanf(“%d”,&n);
int a[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
Thanks for contributing the code Godi