CareerCup

int array1[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 }; 
int array2[20] = { 21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40};

//array1 will contain even. array2 will contain odd.
i=  0; j = 0;
while( i < 20 && j < 20 )
{
    while(i<20 && array[i]%2 == 0)
        i++;
    while(j<20 && array[j]%2 == 1)
        j++;
    //swap only when i < 20 && j < 20 cause there is a possibilty that one could be over before the other.
    if( i<20 && j<20)
    {
        //swap contents of i and j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++; j++;
    }
}

this should b fine.

what an uninteresting problem. i hope i get questions like this.

The solution will fail if negative odd numbers appear in either arrays. The reason: (-231 % 2) does not equals to 1!

{complexity for the solution is O(n^2)}

#include <stdio.h>

#define ODD 1
#define EVEN 0

int main ()
{

int n = 6, i, j, rep = 0, niter = 0, swap;

int ar1[6] = {1, 2, 3, 4, 5, 6}; // Will hold all even numbers
int ar2[6] = {7, 8, 9, 10, 11, 12}; // Will hold all odd numbers

for (i = 0, j = 0 ; rep < n/2 ; niter++)
{
if ((ar1[i]%2 == ODD) && (ar2[j]%2 == EVEN))
{
rep++;
swap = ar1[i];
ar1[i] = ar2[j];
ar2[j] = swap;

i++; j++;
}

else
{
if (ar1[i]%2 == EVEN)
i++;

if (ar2[j]%2 == ODD)
j++;
}
}

for (i = 0 ; i < n ; i++)
printf ("\n ar1[%d] = %d, ar2[%d] = %d", i, ar1[i], i, ar2[i]);

printf ("\nO(n) = %d", niter);

}


O(n) in this algo will be less than or equal to (2*n - 1)..

The code works for negative numbers also when compiled in ANSI C..

Code is in Java but you can get an idea from this. Time complexity O(n)

public static void sortEvenOdd(int[] arr1,int[] arr2){
		 int index1 =0;
		 int index2 =0;
		 int temp;
		 while((index1 = getNextOdd(index1,arr1)) != -1){
			 index2 = getNextEven(index2, arr2);
			 temp = arr1[index1];
			 arr1[index1] = arr2[index2];
			 arr2[index2] = temp;
		 }
	 }
	 public static int getNextOdd(int index,int[] arr){
		 for(int i=index;i<arr.length;i++){
			 if(arr[i]%2==1){
				 return i;
			 }
		 }
		 return -1;
	 }
	 public static int getNextEven(int index,int[] arr){
		 for(int i=index;i<arr.length;i++){
			 if(arr[i]%2==0){
				 return i;
			 }
		 }
		 return -1;
	 }

void rmComma(int a1[], int a2[])
{
int pOdd=0;
int pEven=0;

int length1 = 6;//sizeof(a1)/sizeof(int);//a1 supposed to store odd
int length2 = 6;// sizeof(a2)/sizeof(int);

while(pOdd<length1 && pEven<length2)
{
if(a1[pOdd]%2==0)
{
while(a2[pEven]%2!=1)
pEven++;
swap(a1[pOdd], a2[pEven]);

}
pOdd++;
}
}

void SwapOddEven(int* odd, int* even,int sz){
int j=0;
for(int i=0;i<sz;++i){
if(odd[i]%2==0){
for(;j<sz;++j){
if(even[j]%2==1){
Swap<int>(odd[i],even[j]);
break;
}
}
}
}
}

int i, j, temp, lastIndex;
int array1[10] = {-1,2,3,4,-5,6,7,8,9,10};
int array2[10] = {11,-12,13,14,15,-16,17,18,19,20};

for ( i = 0, lastIndex = 0; i < 10; i++)
{
if(array1[i] % 2 == 0)
{
temp = array1[i];//even number
for(j= lastIndex; j < 10 ; j++)
{
if(array2[j] % 2 == 1) //odd number
{
//exchange
array1[i] = array2[j];
array2[j] = temp;
lastIndex = j;
break;
}
}
}
}

Have 2 pointers, one points at the first non-even number in the array of evens, the other at the first non-odd number in the array of odds. Swap the numbers and increase both pointers (separately) until they find 2 new numbers to be swapped. In-place and linear time. Java:

public static void arrange(int[] e, int[] o) {
	int we=0, wo=0;
	do {
		while (e[we]%2!=0) we++;
		while (o[wo]%2==0) wo++;
		int tmp=e[we];
		e[we]=o[wo];
		o[wo]=tmp;
	} while (wo<o.length&&we<e.length);
}

int a1[]={9,10,11,12,13,14,15,16};
		int a2[]={-1,-2,-3,-4,-5,-6,-7,-8};
		int i=0,j=0;
		while(i<8)
		{
			if(a1[i]%2==0)
			{
				if(a2[j]%2!=0)
				{
					int temp=a1[i];
					a1[i]=a2[j];
					a2[j]=temp;
					i++;
					j++;
				}
				else
					j++;
			}
			else
				i++;
		}
		for(i=0;i<8;i++)
			System.out.print(a1[i]+" ");
		System.out.println();
		for(i=0;i<8;i++)
			System.out.print(a2[i]+" ");