CareerCup

#include <stdio.h>

void print_array(int arr[], int cnt, const char* hdr)
{
    printf("%s\n", hdr);
    for (int i = 0; i < cnt; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void rearrange(int arr[], int cnt)
{
    int cn[3] = {0};
    int k = 0;

    /* Count the number of integers */
    for (int i = 0; i < cnt; i++){
        cn[arr[i]]++;
    }
   
    print_array(arr, cnt, "Array before:");

    /* Now fill back the array with the count of consecutive ints */
    for (int i = 0; i < 3; i++){
        for (int j = 0; j < cn[i]; j++) {
            arr[k] = i;
            k++;
        }
    }

    print_array(arr, cnt, "Array after:");

    return;
}

/*
  Re-arrange an array containing only 0s,1s and 2s, 
  so that all 1s follow all 0s and all 2s follow 1s. 
  e.g. 00000011111111222222. Linear time algorithm.
*/
int main(int argc, char *argv[])
{
    int arr[] = {0,0,0,0,2,1,2,0,2,1,2,1,2,0,1,0,1,0,2,0,1};
    int cnt = sizeof(arr)/sizeof(arr[0]);

    rearrange(arr, cnt);
    return 0;
}

int [] arr = {0,0,0,0,2,1,2,0,2,1,2,1,2,0,1,0,1,0,2,0,1};
int pointer1 = 0,pointer2 = arr.length - 1;
for(int i = 0;i<pointer2;)
{
	if(arr[i]==0)
	{
		if(i == pointer1)
		{//do this to skip the worst case
			i++;
			pointer1++;
		}else
		{
			arr[i] = arr[pointer1];
			arr[pointer1++] = 0;
		}
	}else if( arr[i] == 2 )
	{
		arr[i] = arr[pointer2];
		arr[pointer2--] = 2;
	}else
	{
		i++;
	}
}
System.out.println(Arrays.toString(arr));

<pre lang="" line="1" title="CodeMonkey54578" class="run-this">/*
My algorithm:
1. iterate thru array and count number of 0,1,2
2. based on the counts update the new array as we know the elements in the array are just 0,1,2 using this peice of information form the solution.

*/
public class ArrangeInOrder {





public static void main(String args[])
{
int[] inputArray={0,1,2,0,1,2,2,2,2,1,0,0,0,0};
System.out.println("Initial array is: ");
display(inputArray);
inputArray=Rearrange(inputArray);
System.out.println("ordered array is: ");
display(inputArray);
}

private static void display(int[] inputArray) {
for(int ii=0;ii<inputArray.length;ii++)
{
System.out.println(inputArray[ii]);
}

}

private static int[] Rearrange(int[] inputArray) {
int countZeros=0;
int countOnes=0;
int countTwos=0;
int i= 0;
int j= 0;
int k=0;

for(int ii=0;ii<inputArray.length;ii++)
{
if(inputArray[ii] ==0)
{
countZeros++;
}
if(inputArray[ii] ==1)
{
countOnes++;
}
if(inputArray[ii] ==2)
{
countTwos++;
}
}
System.out.println("zero =" +countZeros + " and ones: "+countOnes+ " and two's: "+countTwos);

for(i=0;i<countZeros;i++)
{
inputArray[i]=0;
System.out.println("entering at location: "+i +" value= 0");
}
System.out.println("i is-----: "+i);
for(j=i;j<countOnes+i;j++)
{
inputArray[j]=1;
System.out.println("entering at location: "+j +" value= 1");
}
System.out.println("j is-----: "+j);
for(k=j;k<countTwos+j;k++)
{
System.out.println("entering at location: "+k +" value= 2");
inputArray[k]=2;
}
System.out.println("k is-----: "+k);
return inputArray;
}

}
</pre>

It is so called Dutch_national_flag_problem and it has a linear and clear solution.

This is a special case of quick sort, which can be done efficiently in-place and by going through the array only once.

void rearrange(int *arr, int size)
{
if (NULL == arr || size <= 0) return;

int head = 0;
int tail = size-1;
int idx = 0;

while (idx <= tail) {
if (arr[idx] == 0) {
arr[head++] = 0;
arr[idx++] = 1;
} else if (arr[idx] == 1)
idx++;
else
swap(arr+(tail--), arr+idx);
}
}

dutch national flag problem....use three pointers...solvable in linear time

Use counting sort. Requires extra space for array of size 3 for this problem, or the range of numbers in the list. e.g. if numbers are 4,3,4,5,6,2,2,2,7,3 then range is (7-2) + 1 = 6.

Hi Geeks Visit My Blog

shashank7s dot blogspot dot com/2011/04/wap-to-given-doubly-linked-list-with dot html

or type query on google "cracking the code shashank" to visit

Count the number of 0s, 1s and 2s. Then print as many 0s out, then 1s, then 2s.

void arrange(int a[],int size)
{
int n1=0,n2=0,n3=0;
for(i=0;i<size;i++)
{
if(i==0)
n1++;
else if(i==1)
n2++;
else
n3++;
}
for(i=0;i<size;i++)
{
if(i<n1)
a[i]=0;
else if(i>=n1 && i<n2)
a[i]=1;
else
a[i]=2;
}
}

Come on
just count all 0s, 1s and 2s in linear time and recreate the array :)

static int[] arranger(int []A){
int num0 = 0;
int num1 = 0;

for (int el:A){
if (el==0)
num0++;
else if (el == 1)
num1++;
}

for (int i=0; i<A.length; i++){
if (i+1<=num0){
A[i] = 0;
}
else if(i+1<= (num0+num1))
A[i] = 1;
else
A[i] =2 ;
}
return A;
}

public static void dutchFlag(int[] array)
    {
	int start = 0;
	int end = array.length - 1;

	int cursor = start;

	while (cursor < end)
	{
	    int current = array[cursor];

	    if (current == 1)
	    {
		swap(array, cursor, start);
		start++;
		cursor++;
	    }
	    else if (current == 3)
	    {
		swap(array, cursor, end);
		end--;
	    }
	    else
	    {
		cursor++;
	    }
	}
    }

void Sort(std::vector<int> & vec) {
  int b = 0;
  int e = v.size() - 1;
  int k = -1;
  while (b <= e) {
    if (v[b] == 0 && b != k +1) {
      std::swap(v[b], v[++k]);
    } else if (v[b] == 2 && b != e) {
      std::swap(v[b], v[e--]);
    } else b++;
  }
}