Sunday, October 30, 2016

Rearrange array such that all odd numbers occupy odd positions

Problem:
Rearrange array such that all odd numbers occupy odd positions and even numbers occupy even position. Order of numbers needs to be maintained without use of extra space.

Solution:
For maintaining the number order, you can apply movement. if odd or even is not in place then find next required number and move other numbers to right. Solution below implements this.
 
public class OddEven {

    public static void main(String[] args) {

        int[] input = {1, 23, 4, 6, 2 , 3, 7, 12, 15, 16, 19, 100};

        System.out.println("Before : ");
        for (int i : input){
            System.out.print(i + " ");
        }

        oddEvenWithoutBuffer(input);

        System.out.println("\nAfter : ");
        for (int i : input){
            System.out.print(i + " ");
        }
    }

    static void oddEvenWithoutBuffer(int[] input) {

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

            int j = i + 1;
            if (i % 2 == 0) {
                if (input[i] % 2 != 0) {
                    while (j < input.length && input[j] % 2 != 0)
                        j++;
                } else continue;
            } else {
                if (input[i] % 2 == 0) {
                    while (j < input.length && input[j] % 2 == 0)
                        j++;
                } else continue;
            }

            if (j < input.length) {
                int temp = input[j];
                for (int m = j; m > i; m--) input[m] = input[m - 1];
                input[i] = temp;
                i++;    //Skip next as its in place, due to movement
            } else
                break;      //No more even or odd remaining.
        }
    }
}


Comments are welcome. Question source geeksforgeeks

No comments:

Post a Comment