Rearranging Array Elements by Parity

Given an array of integers, rearrange the array in (O(n)) time in-place so that all even numbers appear on the left side and all odd numbers appear on the right side. The relative order within the even group and the odd group does not need to be preserved. For example, for the input array ([1, 2, 3, 4, 5, 6]), one valid output is ([6, 2, 4, 3, 5, 1]) where the even numbers (6, 2, 4) appear first and the odd numbers (3, 5, 1) follow. Your task is to implement this rearrangement using a two-pointer strategy.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output the rearranged array as a single line of (n) space-separated integers on standard output (stdout). The even numbers should appear before the odd numbers. The relative order within even or odd segments may vary depending on your implementation.## sample

6
1 2 3 4 5 6

6 2 4 3 5 1