CareerCup

Sum all the N elements, then overwrite the array :)

int main() {
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
    int N = sizeof arr / sizeof *arr; /* 18 */
    int sum = 0;
    int ndx;
    for (ndx=0; ndx<N; ndx++) sum += arr[ndx];
    for (ndx=0; ndx<N-sum; ndx++) arr[ndx] = 0;
    for (ndx=N-sum; ndx<N; ndx++) arr[ndx] = 1;
}

/*  sort an array a[n] containing 0s and 1s with time complexity n and you cant use more than 1 data structure
(you cant use more than 1 array)... the interviewer gave me good 10min to write the code  */

//      Working Code  ||  TIME: O(n)  ||   Space : O(1)

#include<stdio.h>
int main()
{
    int A[20],i,j,n,temp;
    printf("Enter n :");
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&A[i]);
    printf("\n--");
    i=0;
    j=n-1;
    while(i<j)
    {
        while(A[i]==0)
            i++;
        while(A[j]==1)
            j--;
        if(i<j)
        {
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
            i++; j--;
        }
    }// end of while
    printf("\n");
    for(i=0;i<n;i++)
        printf("%d ",A[i]);
    printf("\n");
return 0;
}

start with two pointers, one pointing at the start, other at the end.

value1 value2 newvalue1 newvalue2
0 0 0 0
0 1 0 1
1 1 1 1
1 0 0 1

from the table, the newvalue1 has to be the AND operation of the two values and the newvalue2 has to be the OR operation of the two values.

increment the first pointer only if newvalue1 is 0
decrement the last pointer only if newvalue2 is 1

do this till the two pointers meet/cross each other.

take two variable left and right to store the 1st and last element of the array. start scanning from left to right whenever there is a 1 scan the array from right to left till the right variable is greater than left var or you find a 0.. break if left > right and swap the element at right location with element at left location keep doing until left > right .

Why don't we count all the number of 1's or 0's then create a seperate array with these datas.

#include<iostream>

using namespace std;

void swap(int *a, int *b)
{
	int *tmp = a;
	*a = *b;
	*b = *a;
}
void arrangeOneZeroInArray(int m[], int length)
{
	int high = length - 1;
	int low = 0;
	if(!m || 1 == length)
		return;
	while(low < high)
	{	
		if(m[low] == 1 && m[high] == 0)
		{
			swap(m[low], m[high]);
			low++;
			high--;
		}
		while(0 == m[low])
			low++;
		while(1 == m[high])
			high--;

	}
	for(int i = 0; i < length; i++)
		cout<<m[i]<<" ";
}
void main()
{
	int a[] = {1,0,1,0,1,1,1,0,1};
	int length = sizeof(a)/sizeof(int);
	arrangeOneZeroInArray(a, length);
}

Do we have to use stable sort ? or just do the sorting ?

2 pivots patition:

#include <iostream>
using namespace std;

void swap(int& x, int& y) {
    if(&x == &y)
        return;
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;    
}

void threePartition(int* a, int n) {
    int i = -1, j = n, k = 0;
    while(k < j) {
        if(k == 8 && j == 9) {
            cout << "point" << endl;
        }
        if(a[k] == 0) {
            i++;
            swap(a[i], a[k]);
            k++;
        } else if (a[k] == 2){
            j--;
            swap(a[j], a[k]);
        } else {
            k++;
        }
    }

}

int main() {
    int a[] = {1, 2, 0, 2, 1, 0, 0, 2, 2, 1, 1, 0};
    int n = sizeof(a) / sizeof(a[0]);
    cout << n << endl;
    threePartition(a, n);
    for(int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

int main()
{
int p,q,n=10,a[100];
for(int i=0;i<n;i++) scanf("%d",&a[i]);
p=0;
q=n-1;

while(p<q)
{
	while(a[p]!=1)
	{
		p++;
	}
	
	while(a[q]!=0)
	{
		q--;
	}
	if(p<q)
	{
	a[p]=0;
	a[q]=1;
	}
	p++;
	q--;
	
}

for(int i=0;i<n;i++) printf("%d ",a[i]);


}

public class Zero_Ones {
int a[]={1,1,0,1,1,0,1,0,1,0};
int n=a.length;
int i;
int temp;
public static void main(String[] args) {
new Zero_Ones().go();
}


public void go(){

for(i=0;i<n; i++){
if(a[i]>0){
if(a[i]>a[i+1]){
temp=a[i+1];
a[i+1]=a[i];
a[i]=temp;
}
else{
reuse();
}
}

else{
if(a[i]<a[i+1]){
reuse();
}
}
}

for(int j=0; j<a.length;j++){
System.out.print(a[j]);
}


}

public void reuse(){
temp=a[i+1];
a[i+1]=a[n-1];
a[n-1]=temp;
if(a[i+1]==1){
n=n-1;
i=i-1;
}
else{
i=i-1;
}

}
}

codes-to-problem.blogspot.in/2012/07/sort-array-containing-0s-and-1s-with.html

Just wrote a code in eclipse. Please comment if need to improve.

{{
public static void sortArray( byte[] input )
{
for( int i = 0, j = input.length - 1; i < j ; )
{
if( input[i] == 1 )
{
if( input[j] == 0 )
{
input[i] = 0;
input[j] = 1;
i++;
}

j--;
}
else
{
i++;
}


}
System.out.println(Arrays.toString(input));

}
}}

This may look like counting and will only work if the size of the input array is lesser than the max integer size.

int[] a = new int[]{0,1,1,0,1,0,1,0,0,1,1,1,0};
	int el = 1;
	for(int i=0;i<a.length;i++){
		el=el<<a[i];
	}
System.out.println(Integer.toBinaryString(el-1));
//You could append 0s in front which could be computed  from the array length.

As the array contains only binary 0 & 1. Use OR & AND operators to swap[Not exactly swap].

void sort(int *arr,int size)
{
        int l=0,or,and,h;
        h=size-1;
        while(l<h)
        {       
                while(arr[l]==0)
                        l++;
                while(arr[h]==1)
                        h--;
                if(l<h)
                {
                        or=arr[l]|arr[h];
                        and=arr[l]&arr[h];
                        arr[l]=and;
                        arr[h]=or;
                        l++;h--;
                }
        }
        for(l=0;l<size;l++)
                printf("%d ",arr[l]);
}

ideone.com/6FEU5

public class BinaryArray {
public static void main(String[] args) {
int[] array = {0,1,0,1,0,1,0,1,0,1,0};
int l= 0, r= array.length-1;

while(true){
while(l< array.length && array[l] != 1){
l++;
}
while(r>=0 && array[r] != 0){
r--;
}
if(l < r){
array[l] = 0;
array[r] = 1;
}
else
break;
}

for (int i : array) {
System.out.println(i);
}

}
}

int main()
{
int i,j;
int a[13] ={0,1,1,0,1,0,1,0,0,1,1,1,0};
int *p,*q;
p=a;
q=a+12;
for(;p<q;)
{
if(*p!=0)
*p=0;
p++;
if(*q!=1)
*q=1;
q--;
}
for(i=0;i<13;i++)
printf("%d",a[i]);

Time complexity: o(n)

1. if the current value is 1, throw its index to queue
2. if you got 0 then pop the value from the queue to see the index and swap the current with the one you get from the queue

#include<stdio.h>
#include<string.h>
void main()
{
int a[]={0,1,1,0,1,0,1,0,0,1,1,1,0};
int i,n,j;
j=0;
n=13;
for(i=0;i<n;i++)
{
if((a[i] == 0))
a[j++]=a[i];
}
for(i=j;i<n;i++)
{
a[j++]=1;
}
printf("\n");
for(i=0;i<n;i++)
printf(" %d ",a[i]);
printf("\n");
}

Best optimized code:
1. travers the given array
2. If an element is 1 count ones and make it 0 at the index.
3. Do this until end of the array.
4. Then traverse from end of the array in reversed order and put 1 until number of ones.count.

public void sortArray(int[] arr)
   {
       int countOnes =0;
          for(int i=0;i<arr.length;i++)
          {
                    if(arr[i] == 1)
                    {
                          countOnes++;
                          arr[i]=0;
                    }
          }

          for(int i=arr.length-1;i>= countOnes; i--)
                  arr[i] = 1;
    }

public class SortBinaryArray
{
//Imagine 0 - false , 1 - true
public static void main(String args[])
{
boolean[] bool = new boolean[]{false,true,true,false,true,false,true,false,false,true,true,true,false};
int k =0;
int j =1;
for(int i=0;i<bool.length;i++)
{
if(!bool[i])
{
bool[k++] = false;
}
else
{
int index = bool.length-j++;
if(index > k)
{
bool[index] = true;
}
}
}
for(int i=0;i<bool.length;i++)
{
System.out.println(bool[i]);
}
}
}

if we take 2 counter 1 for zero and one for 1 ...this can be done in one itration nw fill the array by zero upto zero counter -1 nd then remaing by one.....how it? with o(n) complexity

public class Sort
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		int[] arr = {0,1,0,0,0,1,0,0,1,1};
		// arr={0,1,0,0,0,1,0,0,1,1};
		int len=arr.length;
		int i,j=0;
		i=0;
		j=len-1;
		int temp;
		while(i<=j)
		{
			if(arr[i]==0 && arr[j]==1)
			{
				i++;
				j--;
			}
			else if(arr[i]==0 && arr[j]==0)
			{
				i++;
			}
			else if(arr[i]==1 && arr[j]==0)
			{
				temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
				i++;
				j--;
			}
			else
			{
				j--;
			}
		}
		
		for(i=0;i<arr.length;i++)
			System.out.println(arr[i]+" ");
	}

}

//sort an array of 0s and 1s in O(n)
#include<stdio.h>

int main() {
int a[10] = {1, 0, 1, 0, 0, 0, 1, 1, 1, 0};
int p = -1, q;
for(q = 0; q < 10; q++) {
if(p > -1 && a[q] == 0) {
a[q] = a[p] ^ a[q];
a[p] = a[p] ^ a[q];
p++;
} else if(p == -1 && a[q] == 1) {
p = q;
}
}
for(q = 0; q < 10; q++)
printf("%d\n", a[q]);
return 0;
}

public static void sortBinaryArray(int[] A, int s, int e)
{
while(s < e)
{
if (A[s] > A[e])
{
swap(A, s, e);
s++;
e--;
}
else if (A[s] < A[e])
{
e--;
}
else
{
if(A[s] == 1)
{
e--;
}
else
{
s++;
}
}
}
}

public class SortBinaryNumber{
	public static void main(String[] args) throws Exception
	{ 
		int[] a={1,0,1,1,0,1,0,1,0,0,1,1,1,0};
      int count=0;
		for(int i=0;i<a.length;i++)
       {    
    	   if(a[i]==0)
    	   {
    		   a[count++]=0;
    		   a[i]=1;
    	   }
       }
		for(int aa: a)
		System.out.print(aa);
		}
}

public class Sort{

public static void main(String[] args){
int a[]={0,1,1,0,1,0,1,0,0,1,1,1,0};
sort(a);
for(int i : a){
System.out.print(i+" ");
}

}

public static void sort(int[] arr){

int d = arr.length-1;
int s = 0;

while(true){
while(d>=0){
if(arr[d]==0) break;
d--;
}
while(s<=arr.length-1){
if(arr[s]==1) break;
s++;
}

if(d<s) break;
swap(arr,s,d);

}

}

public static void swap(int[] arr,int leftptr , int rightptr){
arr[leftptr]^=1;
arr[rightptr]^=1;
}

}
less than O(N) complexity

Here is the partition logic as pointed by others as well(from k2code.blogspot.in/2010/04/sorting-binary-array.html):

low = 0; 
high = arr.length - 1;
 
while (low < high) {
    while (arr[low] == 0) {
        low ++;
    }
    while (arr[high] == 1) {
        high --;
    }
    if (low < low ) {
        swap arr[low], arr[high]
    }
}

I have used C#.net to solve the problem.

public static void Sort01( ref int[] arr)
        {
            int Left = 0, Right = arr.GetLength(0)-1;

            while(Left<Right)
            {
                if(arr[Left]==0)
                    Left++;
                else if(arr[Right]==1)
                    Right--;
                else 
                {
                    arr[Left]=arr[Left]+arr[Right];
                    arr[Right] = arr[Left] - arr[Right];
                    arr[Left] = arr[Left] - arr[Right];
                    Left++;
                    Right--;
                }
            }   
        }

This is not Exactly Sorting But Arranging All 1s and 0s accordingly, No Extra Space, Can be done in a Linear Time.

#include <stdio.h>
int main()
{
  int a[] = {0, 1,0,1,0,1, 0, 1, 0,1, 0, 1};
  int ct=0, i =0;

  for (i=0;i< (sizeof(a)/sizeof(int)); i++)
  {
    if (a[i])
    {
       if(!a[ct])
       {
         a[ct]= a[i];
         a[i] = 0;
       }
       ct++;
    }
  }
  return 0;
}

Please tell me if this solution is ok or not?

public void sortArray(int arr[])
	{
		
		int p1 = 0 ; 
		int p2 = 0;
		while(arr[p2] !=1)
			p2++;
		for( ;p1<arr.length;p1++)
		{
			if( arr[p1] ==0 &&  p1>p2)
			{
				arr[p1] = 1; 
				arr[p2]=0;
				p2++;
			}
		}
}

public static void sortBinary() {
		int a[]={0,1,1,0,1,0,1,0,0,1,1,1,0};
		int temp,i=0,j=0;
		
		for (j = 0; j < a.length; j++) {
			if(a[i]==1 && a[j]==0) //10
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
				i++;
			}
			else if(a[i]==0)  //00 01
			{
				i++;
			}
			
		}
		
		for (int j2 = 0; j2 < a.length; j2++) {
			System.out.print(a[j2]+" ");
		}

}

public static void sortBinary(int[] arr){
int i=0, j = arr.length -1;
while(i <= j){
if( (arr[i]==0) && (arr[j] ==1)){
i++; j--;
}
else if( (arr[i]==1) && (arr[j]==0)){
arr[i]=0;
arr[j]=1;
i++;j--;
}
else if((arr[i]==0) && (arr[j]==0)){
i++;
}
else if((arr[i]==1) && (arr[j]==1)){
j--;
}
}
}

import java.*; 
import java.util.*;
 
class testQ { 	
	public static void main(String args[]) throws Exception{ 
  			int[] arr = { 1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
			String str = Arrays.toString(arr);
			int k = str.length() - str.replace("0","").length();
				for( int i = 0;i<arr.length;i++){
					arr[i] = ((i>=k) ? 1 : 0);
				}
			System.out.println(Arrays.toString(arr));
	} 
}

import java.*; 
import java.util.*;
 
class testQ { 	
	public static void main(String args[]) throws Exception{ 
  			int[] arr = { 1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
			String str = Arrays.toString(arr);
			int k = str.length() - str.replace("0","").length();
				for( int i = 0;i<arr.length;i++){
					arr[i] = ((i>=k) ? 1 : 0);
				}
			System.out.println(Arrays.toString(arr));
	} 
}

Simple soln. O(n)

public static void main(String[] args){
    int[] arr = {0,1,1,0,1,0,1,0,0,1,1,1,0};
  	sort(arr);
    for(int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
  }
  
  public static void sort(int[] arr){
  
    int i = 0;
    int j = arr.length-1;
    
    while(i <= j){
    
      while(arr[i] == 0)
        i++;
      
      while(arr[j] == 1)
        j--;
      
      if(i < j){
      	swap(arr, i, j);
        i++;
        j--;
      }
    }
  }
  
  public static void swap(int[] arr, int i, int j){
  	int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }