Even numbers at even index and odd numbers at odd index in Java
Given an array of size n. The problem of arranging even numbers at even indexes and odd numbers at odd indexes in an array involves reordering elements such that all even numbers are placed at even indices (0, 2, 4, ...) and all odd numbers are placed at odd indices (1, 3, 5, ...).
Example 1
Input: arr[] = {4, 2, 1, 5, 7, 8}
Output: 4, 1, 2, 5, 8, 7
Explanation: Even numbers 4, 2, and 8 are placed at indices 0, 2, and 4. Odd numbers 1, 5, and 7 are placed at indices 1, 3, and 5.
Example 2
Input: arr[] = {3, 6, 12, 1, 5, 8}
Output: 6, 3, 12, 1, 8, 5
Explanation: Even numbers 6, 12, and 8 are placed at indices 0, 2, and 4. Odd numbers 3, 1, and 5 are placed at indices 1, 3, and 5.
Example 3
Input: arr[] = {7, 4, 6, 9, 2, 3}
Output: 4, 7, 6, 9, 2, 3
Explanation: Even numbers 4, 6, and 2 are placed at indices 0, 2, and 4. Odd numbers 7, 9, and 3 are placed at indices 1, 3, and 5.
Example 4
Input: arr[] = {5, 8, 3, 6, 2, 9}
Output: 8, 5, 6, 3, 2, 9
Explanation: Even numbers 8, 6, and 2 are placed at indices 0, 2, and 4. Odd numbers 5, 3, and 9 are placed at indices 1, 3, and 5.
Brute Force Approach
A brute force approach to arrange even numbers at even indices and odd numbers at odd indices involves iterating through the array and swapping elements to meet the required ordering.
Algorithm
Step 1: Start with a flag swapped set to false.
Step 2: Iterate through the array using a for loop.
Step 3: Check adjacent pairs of elements:
Step 3.1: If an even number is found at an odd index or an odd number is found at an even index, swap the elements and set swapped to true.
Step 4: If no swaps were made in a pass, exit the loop.
FileName: EvenOddIndexBruteForce.java
import java.util.Arrays;
public class EvenOddIndexBruteForce {
public static void arrangeEvenOdd(int[] arr) {
int n = arr.length; // Length of the array
boolean swapped; // Flag to track swaps
do {
swapped = false; // Reset swapped flag
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && arr[i] % 2 != 0 && arr[i + 1] % 2 == 0) {
// Swap even-odd pair
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true; // Set swapped to true
} else if (i % 2 != 0 && arr[i] % 2 == 0 && arr[i + 1] % 2 != 0) {
// Swap odd-even pair
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true; // Set swapped to true
}
}
} while (swapped); // Continue until no swaps are needed
}
public static void main (String[] args) {
int[] arr = {4, 2, 1, 5, 7, 8}; // Input array
arrangeEvenOdd(arr); // Arrange even and odd numbers
System.out.println(Arrays.toString(arr)); // Print the rearranged array
}
}
Output
[4, 1, 2, 5, 8, 7]
Time Complexity: The time complexity of an algorithm is O(n^2), where n is the number of elements in the array. This is because each element might need to be swapped multiple times to reach its correct position.
Space Complexity: The space complexity of an algorithm is O(1). This is because the algorithm uses a constant amount of extra space for temporary variables and flags.
Using ArrayList
An approach that involves separating even and odd numbers into two ArrayLists, then merging them back into the original array in the required order.
Algorithm
Step 1: Create two ArrayLists, evens and odds, to store even and odd numbers.
Step 2: Iterate through the input array, adding even numbers to the evens list and odd numbers to the odds list.
Step 3: Initialize two pointers, evenIndex and oddIndex, to track even and odd indices in the original array.
Step 4: Iterate through the evens list and place even numbers at even indices in the original array using evenIndex.
Step 5: Iterate through the odds list and place odd numbers at odd indices in the original array using oddIndex.
FileName: EvenOddIndexArrayList.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;s
public class EvenOddIndexArrayList {
public static void arrangeEvenOdd(int[] arr) {
// Create two ArrayLists to store even and odd numbers
List evens = new ArrayList<>();
List odds = new ArrayList<>();
// Separate even and odd numbers
for (int num : arr) {
if (num % 2 == 0) { // If number is even
evens.add(num); // Add to evens list
} else { // If number is odd
odds.add(num); // Add to odds list
}
}
// Merge back into the original array
int evenIndex = 0; // Initialize even index
int oddIndex = 1; // Initialize odd index
for (int i = 0; i < evens.size(); i++) { // Iterate through evens list
arr[evenIndex] = evens.get(i); // Place even number at even index
evenIndex += 2; // Move to next even index
}
for (int i = 0; i < odds.size(); i++) { // Iterate through odds list
arr[oddIndex] = odds.get(i); // Place odd number at odd index
oddIndex += 2; // Move to next odd index
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 1, 5, 7, 8}; // Input array
arrangeEvenOdd(arr); // Rearrange even and odd numbers
System.out.println(Arrays.toString(arr)); // Print the rearranged array
}
}
Output
[4, 1, 2, 5, 8, 7]
Time Complexity: The time complexity of an algorithm is O(n), where n is the number of elements in the input array. The algorithm performs a linear scan through the array to separate even and odd numbers and then merges them back into the original array.
Space Complexity: The space complexity of an algorithm is O(n), where n is the number of elements in the input array. The algorithm uses extra space for two ArrayLists to store even and odd numbers.
Using Two-Pointers Approach
The two pointers approach is used to rearrange elements in an array such that even numbers are placed at even indices and odd numbers at odd indices.
Algorithm
Step 1: Initialize two pointers, evenIndex starting at index 0 (even) and oddIndex starting at index 1 (odd).
Step 2: While both pointers are within the array bounds, check the numbers at evenIndex and oddIndex.
Step 2.1: If arr[evenIndex] is even, move evenIndex to the next even index.
Step 2.2: If arr[oddIndex] is odd, move oddIndex to the next odd index.
Step 2.3: If arr[evenIndex] is odd and arr[oddIndex] is even, swap the elements and move both pointers to the next respective indices.
Step 3: Once traversal is complete, the array is rearranged with even numbers at even indices and odd numbers at odd indices.
FileName: EvenOddIndexTwoPointers.java
import java.util.Arrays;
public class EvenOddIndexTwoPointers {
public static void arrangeEvenOdd(int[] arr) {
int evenIndex = 0; // Initialize even index
int oddIndex = 1; // Initialize odd index
int n = arr.length; // Length of the array
while (evenIndex < n && oddIndex < n) { // Traverse until both indices are within bounds
if (arr[evenIndex] % 2 == 0) { // If element at even index is even
evenIndex += 2; // Move to next even index
} else if (arr[oddIndex] % 2 != 0) { // If element at odd index is odd
oddIndex += 2; // Move to next odd index
} else { // If element at even index is odd and element at odd index is even
// Swap the elements
int temp = arr[evenIndex];
arr[evenIndex] = arr[oddIndex];
arr[oddIndex] = temp;
evenIndex += 2; // Move to next even index
oddIndex += 2; // Move to next odd index
}
}
}
public static void main (String[] args) {
int[] arr = {4, 2, 1, 5, 7, 8}; // Input array
arrangeEvenOdd(arr); // Arrange even and odd numbers
System.out.println(Arrays.toString(arr)); // Print the rearranged array
}
}
Output
[4, 1, 2, 5, 8, 7]
Time Complexity: The time complexity of an algorithm is O(n), where n is the number of elements in the array. This is because the algorithm performs a single traversal through the array.
Space Complexity: The space complexity of an algorithm is O(1). The algorithm uses a constant amount of extra space for the two pointers and a temporary variable for swapping elements.