ISC Practicals and Theory - Odd-Even Segregation

Odd-even segregation rearranges an integer array so that all the even numbers come first and all the odd numbers come after them. This program, written in the main method alone, reads 1 to 20 integers, copies the even numbers into a second array and then the odd numbers, and prints the result.

Definition

An integer is even if it leaves remainder 0 when divided by 2, and odd otherwise. Segregation puts every even number before every odd number.

• Zero is even.
• Negative numbers: in Java the remainder takes the sign of the dividend, so -3 % 2 is -1, not 1. A number is therefore tested as odd with % 2 != 0 and as even with % 2 == 0; testing % 2 == 1 would wrongly treat -3 as even.
• Order: this program uses a second array, so the numbers inside each group keep the order in which they were entered (a stable arrangement).

For 5 -3 8 0 -4 7 2 11 -6 the evens in order are 8 0 -4 2 -6 and the odds in order are 5 -3 7 11, so the result is 8 0 -4 2 -6 5 -3 7 11.

Size constraint: the size must be from 1 to 20.

Algorithm

1. Read the number of elements n. If it is not from 1 to 20, print an error message and stop.
2. Read the n elements into the array arr and create the array res of the same size. Set k = 0, the next free position in res.
3. First pass: for every i, if arr[i] % 2 == 0, copy arr[i] to res[k] and add 1 to k.
4. Second pass: for every i, if arr[i] % 2 != 0, copy arr[i] to res[k] and add 1 to k. A negative odd number gives a remainder of -1 (for example -3 % 2 is -1), so the test is != 0 and not == 1.
5. Print res. The even numbers come first and the odd numbers after them, each group in its original order.

Program

Two for loops in main copy the even numbers and then the odd numbers into res; a third loop prints it.

import java.util.Scanner;
public class OddEvenSegregation
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements (1 to 20): ");
        int n = sc.nextInt();                  // number of elements entered by the user (1 to 20)
        if (n < 1 || n > 20)                   // size outside the allowed range
        {
            System.out.println("Invalid input. Size must be from 1 to 20.");
        }
        else
        {
            int[] arr = new int[n];            // original array as entered
            int[] res = new int[n];            // rearranged array: evens first, then odds
            System.out.println("Enter the elements:");
            for (int i = 0; i < n; i++)
            {
                arr[i] = sc.nextInt();
            }
            int k = 0;                         // next free position in res
            for (int i = 0; i < n; i++)        // first pass: copy the even numbers
            {
                if (arr[i] % 2 == 0)
                {
                    res[k] = arr[i];
                    k++;
                }
            }
            for (int i = 0; i < n; i++)        // second pass: copy the odd numbers
            {
                if (arr[i] % 2 != 0)           // -3 % 2 is -1, so do not test == 1
                {
                    res[k] = arr[i];
                    k++;
                }
            }
            System.out.println("Array with even numbers first, then odd numbers:");
            for (int i = 0; i < n; i++)
            {
                System.out.print(res[i] + " ");
            }
            System.out.println();
        }
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 9
Enter the elements:
5 -3 8 0 -4 7 2 11 -6
Array with even numbers first, then odd numbers:
8 0 -4 2 -6 5 -3 7 11 

Enter the number of elements (1 to 20): 4
Enter the elements:
2 4 0 -8
Array with even numbers first, then odd numbers:
2 4 0 -8 

Enter the number of elements (1 to 20): 1
Enter the elements:
7
Array with even numbers first, then odd numbers:
7 

Enter the number of elements (1 to 20): 25
Invalid input. Size must be from 1 to 20.

Dry run

Input: n = 9, arr = [5, -3, 8, 0, -4, 7, 2, 11, -6], k = 0.

First pass (even numbers):

Second pass (odd numbers):

The final array is 8 0 -4 2 -6 5 -3 7 11, which matches the first sample run.

Variations

1. Positive and negative "Rearrange an array so that all negative numbers come before the positive numbers."
2. Zeros and ones "Rearrange an array of 0s and 1s so that all 0s come first."
3. Odd first "Rearrange an array so that all odd numbers come first and the even numbers last."
4. Sorted groups "Segregate the even and odd numbers and sort each group in ascending order."