CareerCup

public void sortArray(int[] array)
	{
		int left = 0;
		int right = array.length - 1;
		
		while(left < right)
		{
			while(array[left] == 0)
				left++;
			while(array[right] == 1)
				right--;
			
			array[left] = 0;
			array[right] = 1;
		}
	}

want to correct a mistake in the above qstn, 0's towards left and 1's towards right..

//cur initialised to starting of array
//n is the no. of elements
//initial state is set to 0 and signifies whether till now any 1 is encountered or not
//once state is changed to 1 and we get any 0 then we bubble it

cur=0;
while(cur<n)
{
if((state==0)&&(a[cur]==1))
state=1;
else if((state==1)&&(a[cur]==0))
{
for(i=cur;(i>=0)&&(a[i-1]==1);i--)
a[i-1]^=a[i]^=a[i-1]=a[i-1]^a[i]; //swapping the elements
}
cur++;
}

// Since the array consists of only 0's and 1's,
1. Initialize two pointers: j = 0, k = array.length - 1;
2. while(j < k) {
if (a[k] < a[j] { // if '0' < '1', swap, for automatic sorting
a[k] = 1;
a[j] = 0;
k--; // point to next swap candidate from right ('0')
}
// if a[k] = '1', a[k] is a swap candidate, if no swap is done for this a[k], we're done with sorting entire array
// If a[j) is 0, it's sorted already, just point to next swap candidate from left ('1')
j++;
}
}

well this can be done in O(len).
following is my implementation

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--) {
char arr[1000];
scanf("%s",arr);
int len=strlen(arr);int one,zero;
for(int j=0; j< len;j++) {

if(arr[j]=='0') zero++;
if(arr[j] == '1') one++;
}
int p1=0,p2=len-1,tmp;tmp=len;
while(1) {
for(int j=p1;j<len;j++) if(arr[j] == '1') {p1=j;break;} else zero--;
arr[p1]='0';zero--;
for(int j=p2;j>=0;j--) if(arr[j]=='0') {p2=j;break;} else one--;
arr[p2]='1';one--;
if(one <=0 || zero <=0) break;
}
printf("%s",arr);

}
return 0;
}

well this can be done in O(len).
following is my implementation

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--) {
char arr[1000];
scanf("%s",arr);
int len=strlen(arr);int one,zero;
for(int j=0; j< len;j++) {

if(arr[j]=='0') zero++;
if(arr[j] == '1') one++;
}
int p1=0,p2=len-1,tmp;tmp=len;
while(1) {
for(int j=p1;j<len;j++) if(arr[j] == '1') {p1=j;break;} else zero--;
arr[p1]='0';zero--;
for(int j=p2;j>=0;j--) if(arr[j]=='0') {p2=j;break;} else one--;
arr[p2]='1';one--;
if(one <=0 || zero <=0) break;
}
printf("%s",arr);

}
return 0;
}

for(i=0;i<n;i++)
{
if(a[i]==1)
{
for(j=i;j<n;j++)
{
if(arr[j]==0)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
break;
}
}
}
}

in place merge sort

int k=arr.size(),int one=0,int zero=0;
for(int i=0;i<k;i++)
{
if(arr[i]) one++;
else zero++;
}
i=0;
while(zero){
arr[i]=0;
i++;
zero--;
}
while(one)
{
arr[i]=1;
i++;
one--;
}

and that's it. it's a basic counting sort.

static String sortZerosOnesString(String input){
		char[]a=input.toCharArray();

		final char zero='0';
		final char one='1';
		
		int i=0;
		int j=a.length-1;
		while(i<j){
			while(a[i]==zero)
				i++;
			while(a[j]==one)
				j--;
			
			if(i<j){
				char temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
			
		}
		
		return new String(a);
	}

{

#include"conio.h"
#include"iostream"
using namespace std;

int main()
{
int a[15]= {0,1,0,0,1,0,1,1,1,0,1};
int i,j=0;
int temp;
for(i=0;i<11;i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
i=0;

}
}
getch();
}




}

#include"conio.h"
#include"iostream"
using namespace std;

int main()
{
int a[15]= {0,1,0,0,1,0,1,1,1,0,1};
int i,j=0;
int temp;
for(i=0;i<11;i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
i=0;

}
}
for(i=0;i<11;i++)
cout<<a[i];
getch();
}

take to pointers starting one from the beginning and one from the end and traverse them towards the center of the array .while doing that compare and swap..u can finish in o(n)

void sortArray (int arr[], int size){

	int i=0, j=size-1;	

	while(i<j){
		
		if(arr[i] == 1 and arr[j]== 0)
			swap(arr,i,j); 
			i++; j--;
		else if(arr[i] == 0)
			i++;
		else if(arr[j] == 1)
			j--;
	}

}

#include<iostream>
using namespace std;

void inplace( int *A , int size )
{
//00010111
int l = 0  ,h=size;

while( l < h )
{

if( A[l] == 0 )
l++;

if( A[h] == 1 )
h--;

if( A[l]== 1 && A[h] == 0  )
{
        A[l] = A[l] ^ A[h];
        A[h] = A[l] ^ A[h];
        A[l] = A[l] ^ A[h];
l++;
h--;
}
}


for( int i=0; i < size ; i++ )
{
        cout << A[i];

}
}


int main()
{

        int Ar[] = {0,1,1,1,1,0,0,0,0,1};
        inplace( Ar , 10 );
return 0;
}

int left =0;
int right= array.lenth();
while(left<right){
if(a[left]>a[right]){
swap(a[left],a[right]);
left++;
right--;
}
else if((a[left]==a[right]) && a[left]==0){
left++;
}else if((a[left]==a[right]) && a[left]==1){
right--;
}else{
left++;
right--;
}
}

I was told to sort it..using concept of binary numbers..

Assuming that the integer array only contains zeros and ones here is another solution

private static void sort1(int[] a) {
		int zerosCount = 0;
		for(int i = 0; i<a.length ; i++) {
			if(a[i] == 0)
				zerosCount++;
		}

		for(int j=0 ; j<a.length ; j++) {
			if(j < zerosCount)
				a[j] = 0;
			else
				a[j] = 1;
		}

}

public void sortArray(int[] array)
{
int left = 0;
int right = array.length - 1;

while(left < right)
{
while(array[left] != 1)
left++;
while(array[right] != 0)
right--;
if(left<right){
array[left] = 0;
array[right] = 1;
}
}
}

public static void sortArray(int[] array)
	{
		int left = 0;
		int right = array.length - 1;
		
		while(left < right)
		{
			while(array[left] != 1)
				left++;
			while(array[right] != 0)
				right--;
			if(left<right){
			array[left] = 0;
			array[right] = 1;
			}
		}
	}

public void sortArray(int[] array)
{
int left = 0;
int right = array.length - 1;

while(left < right)
{
while(array[left] != 1)
left++;
while(array[right] != 0)
right--;
if(left<right){
array[left] = 0;
array[right] = 1;
}
}
}

public static void sortArray(int[] array)
	{
		int left = 0;
		int right = array.length - 1;
		
		while(left < right)
		{
			while(array[left] != 1)
				left++;
			while(array[right] != 0)
				right--;
			if(left<right){
			array[left] = 0;
			array[right] = 1;
			}
		}
	}

int[] arr = {0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,1};

System.out.println("Orginal Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}

for(int i=0;i<arr.length;i++){

for(int j=i;j<arr.length;j++){

if(arr[i]> arr[j]){

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}


}

System.out.println();
System.out.println("Sorted Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}
}

int[] arr = {0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,1};

System.out.println("Orginal Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}

for(int i=0;i<arr.length;i++){

for(int j=i;j<arr.length;j++){

if(arr[i]> arr[j]){

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}


}

System.out.println();
System.out.println("Sorted Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}
}

just count zerros number, ones number, flash buffer and write over with right order O(N)

while(left < right)
{
while(array[left] == 0)
left++;
array[left]=0;
while(array[right] == 1)
right--;
array[right]=1;

}

while(left < right)
{
while(array[left] == 0)
left++;
array[left]=0;
while(array[right] == 1)
right--;
array[right]=1;
}

def movezeros(l):
j=-1
for i in range(len(l)):
if i==0:
j+=1
l[i],l[j]=l[j],l[i]
return l