OppositeParity | Topcoder Archive

Problem Statement

You are given a int[] A. Your task is to rearrange the elements of A in such a way that the parity of each element changes. That is:

The elements of the new array have to remain the same, only their order may change.
For each valid index i, the parity of the element at index i must change.

If there are multiple valid solutions, you may return any one of them. If there are no valid solution, return an empty int[].

Definition

Class:: OppositeParity
Method:: rearrange
Parameters:: int[]
Returns:: int[]
Method signature:: int[] rearrange(int[] A)
(be sure your method is public)

Constraints

A will have between 1 and 1,000 elements, inclusive.
Each element of A will be between 0 and 999, inclusive.

Examples

```
{1, 4, 1, 4, 2, 1, 3, 5, 6, 2}
```
```
Returns: {6, 1, 2, 3, 1, 4, 2, 4, 5, 1 }
```
The original array and the new array written below each other: 1, 4, 1, 4, 2, 1, 3, 5, 6, 2 6, 1, 2, 3, 1, 4, 2, 4, 5, 1 We can easily verify that both properties are satisfied: all elements of the original array are in the new array, and the parity of the element at each index changed (e.g., at index 0 the odd number 1 was replaced by the even number 6).
```
{1, 1, 2}
```
```
Returns: { }
```
This array has no valid rearrangement. In particular, {2, 2, 1} is not a valid solution because it does not contain the same elements - it has more 2s and fewer 1s than the original array.
```
{3, 1, 4, 1, 5, 9}
```
```
Returns: { }
```
No solution here either.

{27, 18, 281, 828, 45, 90, 452, 3}

Returns: {452, 3, 90, 45, 828, 281, 27, 18 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.