Thursday, January 15, 2009

Monday, January 05, 2009

Arrange 0's & 1's

Problem Statement:
-------------------

An array of size n among which there are n/2 0s and n/2 1s arranged in random order.
Arrange all the 1s to left and all 0s to right but it needs to be
stable i.e., the order of 1s and 0s in the i/p array should be maintained.

Expected Complexity:
--------------------------------
O(N) with constant space.


Pseudocode:
--------------------

1. Have two counters, count1 = 0 and count2 = (n/2)+1
2. Traverse thru the array, if(arr[ i ] == 1) { arr[ i ] = count1++;} else { arr[ i ] = count2++ };
3. At the end of the traversal, you have array filled with numbers 0 to n-1


Now the problem reduces to sorting and array of n numbers which has elements from 0 to
n-1 occuring only once which can be done in O(n).



for(j = 0; j <= 1; j++)
{
for(i = 0; i<n; i++)
{
if(arr[ i ] != i)
{
swap(arr[ i ], arr[ arr[ i ] ]);
}
}
}
</pre>


Note: j loop runs only twice irrespective on 'n' and has constant complexity. The order of this whole loop is 2*n = O(n).


4. After the array is sorted, Again traverse thru the array and make elements arr[0] to
arr[n/2] to '1' and arr[(n/2)+1] to arr[n] as '0'.


Space complexity is constant and time complexity is O(step2) + O(step3) + O(step4) = n + 2n +n = 4*n = O(n).


Solution #1 (Stable):
------------------------

<pre name='code' class='cpp'>
#include<iostream.h>

int a[] = { 1,0,0,0,1,1,1,0,0,1};
#define _SIZE sizeof(a)/sizeof(a[0])


/* Helper Function */
void printArray()
{
for(int i=0;i<_SIZE; ++i)
cout<<a[i]<<" ";

cout<<endl;
}

int main()
{

int countOne = 0;
int countZero = (_SIZE)/2;
int i = 0;

/* Fill the array with numbers from 1 to N */
for(i=0; i < _SIZE; ++i)
{

if(a[i] == 1)
{
a[i] = countOne;
countOne++;
}
else
{
a[i] = countZero;
countZero++;
}
}
printArray();

/* Swap the number and make it a sorted one */
for(int j = 0; j< 2; ++j)
{
for(i=0; i < _SIZE; ++i)
{
if(a[i] != i)
{
int temp = a[i];
a[i] = a[a[i]];
a[temp] = temp;
}
}


}


printArray();

/* Fill the 1st N/2 elements with 1 */
for(i=0; i<_SIZE/2; ++i)
a[i] = 1;


/* Fill the last N/2 elements with 1 */
for(i=_SIZE/2; i<_SIZE; i++)
a[i] = 0;

printArray();

return 0;
}

</pre>


Solution #2 (UnStable):
-----------------------------------


Here is a small variation of the quick sort to solve the same problem but this solution is not stable. So I prefer #1.


<pre name='code' class='cpp'>
#include<iostream.h>
using namespace std;
#define _SIZE sizeof(a)/sizeof(a[0])

void swap(int *a, int l, int r)
{
cout<<"Swaping "<<l<<" "<<r<<endl;

if(a[l] != a[r])
a[l] ^= a[r] ^= a[l] ^= a[r];

return;
}


bool compare_1_upper(int *a, int u, int p)
{

return (a[u] == p);
}

bool compare_1_lower(int *a, int l, int p)
{
return (a[l] < p);
}


bool compare_0_upper(int *a, int u, int p)
{
return (a[u] > p);
}

bool compare_0_lower(int *a, int u, int p)
{
return (a[u] == p);
}

bool (*funcPtr_upper)(int *, int, int) = 0;
bool (*funcPtr_lower)(int *, int, int) = 0;

void qPartition(int *a, int low, int upper)
{
int pivot = a[low];
int l = low - 1;
int u = upper + 1;
if(a[low])
{
funcPtr_upper = compare_1_upper;
funcPtr_lower = compare_1_lower;
}
else
{
funcPtr_upper = compare_0_upper;
funcPtr_lower = compare_0_lower;
}
while(1)
{
while(funcPtr_upper(a, --u, pivot));
while(funcPtr_lower(a, ++l, pivot));
if(l<u)
swap(a, l, u);
else
return;
}
return;
}
int a[] = { 1,1,1,1,1,0,0,1};
void print()
{
for(int i=0; i< _SIZE; ++i)
cout<<a[i]<<" ";
cout<<"\n";
}
int main()
{
print();
qPartition(a, 0, _SIZE - 1);
print();
return 0;
}