CareerCup

O(n) algo
Take two pointers and point to first and second element respectively
1. If first pointer points to odd number and second points to even, they are in correct position so move both pointers by two.
2. If first pointer points to even number and second points to odd, swap values and move both pointers by two.
3. If exactly one pointer moves to wrong position i.e first pointer points to even on second pointer points to odd, move the pointer in correct position by two places and go to step 1.

EDIT : To maintain the order, we can change the third condition by swapping the values at wrong pointer and right pointer before moving forward by two places.

The original question is questionable. What about an array containing more odd/even numbers than even/odd ones? The extreme case is all numbers are even or odd.

Do not waste your time until the guy posting it comes forward to clarify it.

If the order of numbers doesn't change that what is the alternative, do we leave the positions blank which is again equivalent to having initialization values there. For example: 1,2,4,7
a[0] = 1
a[1]= ??
a[2]= 2
a[3] = ??

class ArrayRearrange {
	void checkArray(int[] array) {
		int oddCount = 0;
		int evenCount = 0;
		for (int entry : array) {
			if (entry % 2 == 0) {
				++evenCount;
			} else {
				++oddCount;
			}
		}
		if (oddCount != evenCount) {
			throw new IllegalArgumentException("there should be same number of odd an even entries");
		}
	}
	
	public void swapOddEven(int[] array) {
		checkArray(array);
		int lastEvenImbalance = -1;
		int lastOddImbalance = -1;
		for (int i = 0; i < array.length; ++i) {
			if (array[i] % 2 == 0) {
				if (i % 2 != 0) lastEvenImbalance = i;
			} else {
				if (i % 2 == 0) lastOddImbalance = i;
			}
			if (lastEvenImbalance != -1 && lastOddImbalance != -1) {
				int temp = array[lastEvenImbalance];
				array[lastEvenImbalance] = array[lastOddImbalance];
				array[lastOddImbalance] = temp;
				lastEvenImbalance = -1;
				lastEvenImbalance = -1;
			}
		}
	}
	
	public static void main(String[] args) {
		int[] array = {1,2,3,4};
		ArrayRearrange arrayRearrange = new ArrayRearrange();
		arrayRearrange.swapOddEven(array);
		for (int entry : array) {
			System.out.println(entry);
		}
	}
}

static void Main(string[] args)
        {
            int[] arr = {1,1,3,4,1,6,5,8};
            for (int i = 0, j = 1; j < arr.Length; i++, j++)
            {
                if (i % 2 == 0 && arr[i] % 2 != 0)
                {
                    while (arr[j] % 2 != 0)
                    {
                        j++;
                    }
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    if (j != arr.Length - 1)
                    {
                        j = i + 1;
                    }
                }
                else if(i%2 !=0 && arr[i]%2 == 0)
                {
                    while (arr[j] % 2 == 0)
                    {
                        j++;
                    }
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    if (j != arr.Length - 1)
                    {
                        j = i + 1;
                    }
                }
            }
        }

Order of numbers are not restored but still need to understand the Q

Assumptions:
Assume the problem is referring to a 1-indexed array (implementation could be 0 indexed, but the "first" spot is odd)
There are the floor[Length/2] even numbers and ceiling[length/2] odd numbers (so every number has a place).
By "order of numbers should not change", I'll take that to mean that if Ai and Ak are both odd or both even and i < k in the original, then Ai will be before Ak in the final output. I.e the order of odds and evens are maintained separately.

Algo:
Two pointers. OddPtr starts at 1, EvenPtr at 2
"Good" check for OddPtr => Arr[OddPtr] % 2 = 1
"Good" check for EvenPtr => Arr[EvenPtr] % 2 = 0

If they're both wrong, switch and go to finishing step.
If OddPtr is wrong, move to EvenPtr + 1 and check if good. If so, walk the value and pointer back to original position of OddPtr (swap all elements down along the way, instead of direct swap). If EvenPtr + 1 not odd, OddPtr++ and try again.
If EvenPtr is wrong, EvenPtr++ and check. Do the same thing as OddPtr.

Finishing: Add two to OddPtr and EvenPtr, until EvenPtr > Arr.Length().

Walkthrough:
() = OddPtr
[] = EvenPtr

Initial array: 2,4,1,3,5,7,6,8
Step 1: (2),[4],1,3,5,7,6,8 => OddPtr is wrong. Go to EvenPtr+1=> 2,[4],(1),3,5,7,6,8. Valid, walk 1 and OddPtr back (EvenPtr stays at pos2), giving (1),[2],4,3,5,7,6,8. Move pointers

Step 2: 1,2,(4),[3],5,7,6,8 => Both wrong, swap & finish.

Step 3: 1,2,3,4,(5),[7],6,8 => EvenPtr wrong. Move up one. 6 is even, so walk it back & finish.

Step 4: 1,2,3,4,5,6,(7),[8] => Good. Finish, which hits terminal condition, done.

Code:

inline bool CheckOdd(int n) { return (n % 2 == 1); }
inline bool CheckEven(int n){ return (n % 2 == 0); }
inline void Swap(int *arr, int ptr1, int ptr2) { int temp = arr[ptr1]; arr[ptr1] = arr[ptr2]; arr[ptr2] = temp }

public int* ShuffleOddsAndEvens (int* arr, int arrLength)
{
  int OddPtr = 0;
  int EvenPtr = 1;
  
  while(EvenPtr < arrLength)
  {
    if( !CheckOdd(arr[OddPtr]) && !CheckEven(arr[EvenPtr])) { swap(arr, OddPtr, EvenPtr); }
    else if( !CheckOdd(arr[OddPtr])
    {
      int originalOddPtr = OddPtr;  
      OddPtr = EvenPtr + 1;
      while(OddPtr < arrLength && !CheckOdd(arr[OddPtr]))
      {
          OddPtr++;
      }
      while(OddPtr > originalOddPtr)
      {
         swap(arr, OddPtr, OddPtr-1);
         OddPtr--;
       }  
     }
     else if (!CheckEven(arr[EvenPtr]))
     {
        //Same as above, just Even
      }
      OddPtr += 2;
      EvenPtr += 2
  }
  return arr;
}

Not sure if the code is 100%, but the algo should work

/*
Working Code in C
*/
#include <stdio.h>

enum marker {is_inactive = 0, is_odd = 1, is_even = 2, is_both = 3};
void swapandshift(int first, int last);
void printArray();

int number[] = {3, 4};
int size = (int)sizeof(number)/(int)sizeof(int);

int main() {
	int even = 0;
	int odd = 1;
	enum marker swapmarker = is_inactive;
	while(even < size && odd < size){
		
		if(number[even]%2 == 0 && number[odd]%2 != 0 && swapmarker == is_inactive) {
			even = even +2;
			odd = odd + 2;
		}
		else if(number[even]%2 != 0 && number[odd]%2 != 0){
			swapmarker = is_even;
		}
		else if(number[even]%2 == 0 && number[odd]%2 != 1){
			swapmarker = is_odd;
		}
                else if(number[even]%2 != 0 && number[odd]%2 != 1){
                        swapmarker = is_both;
                }
			switch(swapmarker) {
				case 1 : if(number[even]%2 == 1){swapandshift(odd, even);odd = odd+2;}even++;break;
				case 2 : if(number[odd]%2 == 0){swapandshift(odd, even);even = even+2;}odd++;break;
				case 3 : swapandshift(even, odd);even = even+2;odd = odd+2;
                                default : break;
			}
	}
	printArray();
	return 0;
}
void swapandshift(int first, int last) {
	int temp = number[first];
	number[first] = number[last];
	while(last > first+1) {
		number[last] = number[last-1];
		last--;			
	}
	number[last] = temp;
}
void printArray() {	
	int index = 0;
	printf("{");
	while(index < size-1) {
		printf("%d, ", number[index]);
		index++;
	}
	printf("%d}", number[index]);
}

//Logic
//
//For entire array.
//1. check if at current position correct number is placed
// if yes then continue
// if NOT then follow 2 to 5
//2. find the position of the correct number let this position be jposition
//3. store jpositionth number in temp
//4. shift array from current position to jposition
//5. store temp at current position...


//code

#include "iostream"
using namespace std;
void print(int a[],int size)
{

for (int i =0;i<size;i++)
cout << a[i] << "==>";
}

void ArrangeArrayEvenOdd(int a[],int size)
{
	for(int i = 0; i<9; ++i)
	{
		//step 1
		if(i%2 == a[i]%2)
			continue;
		else
		{//step2
			int j = 1+i;
			if(i%2 ==0)
			{
				while(a[j]%2 != 0)
					++j;
			}
			else
			{
				while(a[j]%2 !=1)
					++j;
			}
			//step 3
			int temp = a[j];
			//step 4 shifting array
			int k = j;
			while(k>i)
			{
				a[k] = a[k-1];
				k--;
			}
			//step 5 correct element at correct position
			a[i] = temp;
		}
	}
}
int main ()
{

int a[] = {1,5,7,2,3,8,6,0,10};
print(a,9);
cout << endl;
cout << endl;
ArrangeArrayEvenOdd(a,9);
print(a,9);
return 0;
}

After seeing so many comments , I felt that I need to give more details. Consider the array below:

a[ ]={2,8,1,9,10,5,7,11,13}

output={1,2,9,8,5,10,7,11,13}. Here the order of odd and even numbers are same. The one which is more in number will be assembled at last. I hope the qns is now clear.

void arrangeOddEven(int a[])
{
int size=a.length;
for(int i=0;i<size;i++)
{
if((i+1)%2==1 && a[i]%2==0)
{
int j=i+1;
while(j<size && a[j]%2==0) j++;

if(j<size)
{
int t=a[j];
while(j>i) {a[j]=a[j-1]; j--;}
a[j]=t;
}


}
else if((i+1)%2==0 && a[i]%2==1)
{
int j=i+1;
while(j<size && a[j]%2==1) j++;

if(j<size)
{
int t=a[j];
while(j>i) {a[j]=a[j-1];j--;}
a[j]=t;
}


}

}
}

package samplejava;

public class Arrayoddevensort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int a[]={2,8,1,9,10,5,7,11,13};
int b[]=new int[a.length];
int odd[]=new int[6];
int even[]=new int[3];

for(int i=0,k=0,n=0;i<a.length;i++){

if(a[i]%2==0)
{
even[k]=a[i];
//b[i]=even[k];
k++;
}
else
{
odd[n]=a[i];
//b[i]=odd[n];
n++;
}
}

for(int i=0,k=0,n=0;i<b.length;i++){
if((i)%2==0)
{
//even
if(k<even.length)
{
b[i]=even[k];
k++;
}
else{
b[i]=odd[n];
n++;
}
}
else{
if(n<odd.length){
b[i]=odd[n];
n++;
}
else
{
b[i]=even[k];
k++;
}
//odd
}
}
for(int i=0;i<b.length;i++)
{
System.out.println("SORTED ARRAY:"+b[i]);
}


}


}

Stop posting your own stupid problems.

package testpack;

//there should be same number of even and odd numbers

public class Program7 {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = { 1, 2, 3, 4 };

int eve = 0, odd = 0, ce = 0, co = 0;

for (int i = 0; i < a.length; i++) {
if (a[i] % 2 == 0) {
++eve;

} else {
++odd;

}
}

int[] eve_arr = new int[eve];
;
int[] odd_arr = new int[odd];

for (int i = 0; i < a.length; i++) {
if (a[i] % 2 == 0) {

eve_arr[ce] = a[i];
ce++;
} else {

odd_arr[co] = a[i];
co++;
}
}

// System.out.println(eve_arr.length+" "+odd_arr.length);

/*
* int i_ = 0, e1 = 0, o1 = 0;
*
* while(i_ <= a.length){
*
*
* if( i_ % 2 == 0){ System.out.println(e1); a[i_] = eve_arr[e1]; e1++;
*
* } else{ a[i_] = odd_arr[o1]; o1++;
*
* }
*
*
*
* i_++;
*
*
*
* }
*/

int m = 0, n = 1;
for (int i = 0; i < odd_arr.length; i++) {

a[n] = odd_arr[i];
n = n + 2;
}

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

a[m] = eve_arr[i];
m = m + 2;
}

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

}
}

Yes, this question has to have a constraint. The constraint being the presence of equal no. of even and odd numbers...or else u end up facing ArrayIndexOutOfBoundsException..which took most of my time to rectify :-/

#include <stdio.h>
#include <stdlib.h>

//The idea behind the algorithm :
//If even occurs at even OR odd occurs at odd, go to next
//Else stop at wrong index, scan elements after it based on
// a. If elements after that occuring correctly, then just swap with wrong
// b. Else if element not correct and index same type as wrong one, then skip
// c. Else if index of other type, then swap and move to next element
// The method works fine for the cases in the discussion.

main() {
	int *arr;;
	int i, j, k, l, n;

	//Taking input array
	scanf("%d", &n);
	arr = (int *)malloc(sizeof(int)*n);
	for(i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	i = -2;
	j = -1;
	k = 0;
	l = 0;

	//go till end of loop
	while(k < n) {
		//if at even position, an odd element occurs or vice versa
		if((k+arr[k]) & 1L)
		{
			if(l <= k)
				l = k+1;
			else
				l++;
			
			//if right positions, even at even OR odd at odd
			if(!((l+arr[l]) & 1L))
			{	
				int temp = arr[k];
				arr[k] = arr[l];
				arr[l] = temp;
			}
			//if wrong positions
			else
			{
				//if type different from k type
				if((k+l) & 1L)
				{
					int temp = arr[k];
					arr[k] = arr[l];
					arr[l] = temp;
					k++;
				}
			}
		}
		//if the eleeent if right, even at even OR odd at odd
		else
			k++;
	}

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

	return 0;
}

java solution:


public class ArrayOddEven {
public static void main(String[] args) {
int [] a= {2,8,1,9,10,5,7,18,12,13};
ArrayOddEven aoe = new ArrayOddEven();
for(int i=0,j=1;i<a.length && j<a.length;)
{
if(i<a.length && j<a.length){
if((a[i]%2 == 0)&& (a[j]%2 != 0)){
i = i+2;
j = j+2;
}
else if((a[i]%2 != 0) && (a[j]%2 == 0)){
aoe.swap(i, j, a);
i = i+2;
j = j+2;
}
else if((a[i]%2 != 0) && (a[j]%2 !=0)){
int k = i+2;
while(k<a.length && a[k]%2 != 0){
k++;
}
if(k >= a.length){
System.out.print("array finished");
}
else{
int temp = a[k];
while(k>i){
a[k] = a[k-1];
k--;
}
a[k] = temp;
}
i = i+2;
j = j+2;
}
else if((a[i]%2 == 0) && (a[j]%2 == 0)){
int m = j+1;
while(m<a.length && a[m]%2 == 0){
m++;
}
if(m >= a.length){
System.out.print("array finished");
}
else{
int temp = a[m];
while(m>j){
a[m] = a[m-1];
m--;
}
a[m] = temp;
}
i = i+2;
j = j+2;
}
}
}

for(int k : a)
System.out.print(", "+k);
}

public void swap(int i,int j,int []a){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

I don't see a way of doing this in-place without an additional data structure like a stack or a simulated one through recursion. Below is my recursive version. Basically pos, numEven and numOdd are all 0 initially. The idea is to store arr[pos] as a variable, then rely on recursion to properly place all numbers in the rest of the array. After the recursive call, we can then put arr[pos] in the appropriate place. We know where to place it because we keep track of how many even & odd numbers we have seen so far.

Note that I am assuming there's enough even and odd numbers to properly place in the array.

static void rearrange(int[] arr, int pos, int numEven, int numOdd) {
  if(pos >= arr.length)
    return;
  int n = arr[pos];
  if(n%2 == 0) {
    rearrange(arr, pos+1, numEven+1, numOdd);
    arr[2*numEven] = n;
  } else {
    rearrange(arr, pos+1, numEven, numOdd+1);
    arr[2*numOdd+1] = n;
  }
}