CareerCup

#include<iostream.h>
void zerothenone(int *a,int n)
{
     int i=0,j=n;
     while(i<j)
{ 
     if(a[i]==0 && a[j]==1)
     { i++; j--; }
     if(a[i]==0 && a[j]==0)
     { i++; }
     if(a[i]==1 && a[j]==0)
     { int t = a[i];
       a[i] = a[j];
       a[j] = t;
       i++; j--;
     }
     if(a[i]==1 && a[j]==1)
     { j--;}
     
}
 }
int main()
{ int c[10] = {0,0,1,0,1,1,1,0,0,};
  int l = sizeof(c)/sizeof(c[0]);
  zerothenone(c,l-1);
  for(int i=0;i<=9;i++)
  { cout<<c[i]<<"\t";
  }
  getchar();
  return 0;
}

Traverse the array from left to right and keep on storing the number of 1s till that index at each status.
Once traversal is done, traverse it from right to left, if the current index is more than 0 then replace current element with 1 and decrease the next element by 1. If you hit a 0 then all elements left to it should be 0.

public class ZeroOneSeparator {
	
	public static void zeroOneSeparator(int[] inputArr){
		for(int i = 1; i < inputArr.length; i++){
			inputArr[i] = inputArr[i-1] + inputArr[i];  
		}
		for(int i = inputArr.length - 1; i > 0 ; i--){
			if(inputArr[i] > 0){
				inputArr[i-1] = inputArr[i] - 1;
				inputArr[i] = 1;
			}else
				inputArr[i-1] = 0;
		}
		for(int i = 0; i < inputArr.length; i++)
			System.out.print(inputArr[i]);
	}
	
	public static void main(String[] args) {
		int[] inputArr1 = {1,0,1,0,1,1};
		ZeroOneSeparator.zeroOneSeparator(inputArr1);
		System.out.println("");
		int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1};
		ZeroOneSeparator.zeroOneSeparator(inputArr2);
		int[] inputArr3 = {};
		System.out.println("");
		ZeroOneSeparator.zeroOneSeparator(inputArr3);
		int[] inputArr4 = {0,0,0,0,0,0};
		System.out.println("");
		ZeroOneSeparator.zeroOneSeparator(inputArr4);
		int[] inputArr5 = {0,1,0,1,0,1,0,1};
		System.out.println("");
		ZeroOneSeparator.zeroOneSeparator(inputArr5);
		int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0};
		System.out.println("");
		ZeroOneSeparator.zeroOneSeparator(inputArr6);
	}

}

1) Count the number of 0's and 1's. (One iteration and two variables)
Let # of zeros = n and # of ones = m.
2) put n zeros in front and m ones at the back.

Example: 011001
1)Count the number of zeros and ones
# of zeros = 3
# of ones = 3

2) The first 3 places are zeros
000XXX
3) The last 3 places are ones
000111

public class xyz {

/**
* @param args
*/
public static void main(String[] args) {
int array[]={1,1,1,1,0,0,0};
for(int i=0;i<array.length;i++)
{if(array[i]==1){

for(int j=i+1;j<array.length;j++)
{
if(array[j]==0){
array[i]=0;
array[j]=1;
break;
}
}
}

}
for(int i =0;i<array.length;i++)
System.out.println(array[i]);
}

}

public static void sortBinary(int []s) {
		
		 int st = 0  ,end = s.length-1; 
		 int t  ; 
		 
		 while ( st < end) {
			 if ( s[st] !=1) st++ ;
			 
			 if ( s[end] !=0) end--;
			 
			 if (s[st] ==1 && s[end] == 0) {	 
				 t = s[st] ; 
				 s[st] = s[end] ; 
				 s[end] = t ; 
				 st++ ; end-- ; 
			 }
		 }	
		 
			 for (int i:s)
				 System.out.print(i);
			 
			 System.out.println("");	
	}

sortBinary(new int [] {0,1,1,1,1,1,1,0,0,0,1});

use quicksort and it will be Olog2N

void fun(int *arr,int n)
{
        int i,j=n-1;
        for(i=0;i<=j;)
        {
                if(arr[i]==1)
                {
                        swap(&arr[i],&arr[j]);
                        j--;
                }
                else i++;
        }
        for(i=0;i<n;i++)
        {
                printf("%d ",arr[i]);
        }
}
 
int main()
{
        int arr[]={0,1,1,0,0,1};
        fun(arr,sizeof(arr)/sizeof(arr[0]));
 
        return 0;
}

#include<stdio.h>
#include<stdlib.h>

int main()
{
int i=0,j,n;
printf("enter the no of values\n");
scanf("%d",&n);
int *a=(int *)malloc(sizeof(int)*n);
printf("enter the nos.\n");
while(i<n)
scanf("%d",&a[i++]);
i=0,j=n-1;
while(i<=j)
{
if(a[i]==1 && a[j]==0)
{
a[i]=0;
a[j]=1;
i++;
j--;
}
else
{
if(a[i]==0)
i++;
if(a[j]==1)
j--;
}
}
i=0;
while(i<n)
printf("%d ",a[i++]);
return;
}

a simple way, O(n/2)
int[] arrZerosOnes = { 0,1,0,1,0,1,1 };
int firstOne = -1;
int oneCounter = 0;
int j = arrZerosOnes.Length - 1;
for (int i = 0; i < arrZerosOnes.Length/2; i++)
{
if (arrZerosOnes[i] == 1)
{
if (oneCounter == 0)
{
firstOne = i;
oneCounter = 1;
}
else
{
oneCounter++;
}


}
if (arrZerosOnes[j]==0)
{
if(oneCounter>0)
{
arrZerosOnes[j] = 1;
arrZerosOnes[firstOne++] = 0;
}
}
j--;
}

no warranty
	public static void sortBinary(int[] s) {

		int t;
		int cnt;

		for (;;) {
			int st = s.length - 2, end = s.length - 1;

			while (st > -1) {

				if (s[end] == 0 && s[st] == 1) {
					t = s[st];
					s[st] = s[end];
					s[end] = t;

				}
				st--;
				end--;
			}

			st = 0;
			end = 1;
			while (end < s.length) {

				if (s[end] == 0 && s[st] == 1) {
					t = s[st];
					s[st] = s[end];
					s[end] = t;

				}

				st++;
				end++;
			}

			cnt = 0;
			for (int i = 0; i < s.length - 1; i++)
				if (s[i] != s[i + 1])
					cnt++;

			if (cnt == 1)
				break;

		}
		for (int i : s)
			System.out.print(i);

		System.out.println("");
	}


sortBinary(new int [] {1,1,1,0});

public static void sortBinary(int[] s) {

		int t;
		int cnt;

		for (;;) {
			int st = s.length - 2, end = s.length - 1;
			while (st > -1) {
				if (s[end] == 0 && s[st] == 1) {
					t = s[st];
					s[st] = s[end];
					s[end] = t;
				}
				st--;end--;
			}
			st = 0;end = 1;
			while (end < s.length) {
				if (s[end] == 0 && s[st] == 1) {
					t = s[st];
					s[st] = s[end];
					s[end] = t;
				}
				st++;end++;
			}
			cnt = 0;
			for (int i = 0; i < s.length - 1; i++)
				if (s[i] != s[i + 1])
					cnt++;
			if (cnt == 1)
				break;
		}
		for (int i : s)
			System.out.print(i);

		System.out.println("");
	}

sortBinary(new int [] {1,1,1,0});

Bubble sort is enough

public static void doIt(int[] a) {

		int tmp ; 
		for (int i = 0 ; i < a.length; i++)
			for (int j =0 ;j< a.length-1 ; j++)
				if ( a[j] >a[j+1]){
					
					tmp = a[j];
					a[j] =a[j+1] ;
					a[j+1] = tmp;
				}
		
		for (int i : a)
			System.out.print(i);

		System.out.println("");
	}

doIt(new int [] {0,1,1,1,0,1,1,0,0,0,1,0});

simple method ,O(n/2)

#include<iostream.h>
#define size 6
void swap(int *x,int *y){
*x=*x+*y;
*y=*x-*y;
*x=*x-*y;
}
void main(){
int i,j=0,k=0,one,zero,arr[]={0,1,1,0,0,1};
cout<<"Orig: ";
for(i=0;i<size;i++)
cout<<arr[i]<<" ";
for(i=0;i<=size/2;i++){
for(;j<size/2;j++)
if(arr[j]==1){
one=j;
break;
}

for(;k<size/2;k++)
if(arr[size-1-k]==0){
zero=size-1-k;
break;
}
swap(&arr[one],&arr[zero]);
}

cout<<"\nRes : ";
for(i=0;i<size;i++)
cout<<arr[i]<<" ";
}

They expecting program using shift operator and bit operations

#include <stdio.h>

void segregate_zero_one(int * a, int len)
{
int itr = 0;
int last_one = -1;
for (itr = 0 ; itr < len ; itr++)
{
if (a[itr] == 0 && last_one >= 0)
{
a[itr] = 1;
a[last_one] = 0;
last_one++;
}
else if (a[itr] == 1 && last_one == -1)
{
last_one = itr;
}
}
}


void print(int * a, int len)
{
int itr = 0;
for (itr= 0 ; itr < len ; itr++)
{
printf("%d ", a[itr]);
}
printf("\n");
}

int main()
{
int k[14] = {0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1};
print(k, 14);
segregate_zero_one(k, 14);
print(k, 14);
}

public class Bedmas {
public static void main(String[] args) throws NumberFormatException, IOException
{BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int size;
size=Integer.parseInt(br.readLine());
int[] a=new int[size];
for(int i=0;i<size;i++)
{a[i]=Integer.parseInt(br.readLine());}
int[] ones=new int[size/2];
int g=0,h=0;
int[] zeroes=new int[size/2];
for(int i=0;i<size/2;i++)
{if(a[i]==1){ones[g]=i;g++;}
else{}
}
for(int i=0;i<size/2;i++)
{if(a[size-1-i]==0){zeroes[h]=(size-1-i);h++;}}
for(int i=0;i<h;i++)
{int j=a[ones[i]];
a[ones[i]]=a[zeroes[i]];
a[zeroes[i]]=j;}
for(int i=0;i<size;i++){System.out.println(a[i]);}
}
}

Use counting sort and get the answer .

public class SortingZeroToOne {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int parentIndex = -1;
int currentIndex = -1;
int[] arr = {0, 1, 1, 0, 0, 1};
for(int i = 0; i<arr.length; i++){
if(arr[i] == 0){
parentIndex = currentIndex;
currentIndex = i;
if(parentIndex != -1){
int temp = arr[parentIndex + 1];
arr[parentIndex + 1] = arr[currentIndex];
arr[currentIndex] = temp;
currentIndex = parentIndex +1;
}}else{
continue;
}}
for(int i = 0; i<arr.length; i++){
System.out.print( " " +arr[i]);
}}}