Parth's OCD Challenge

Parth, a budding programmer, has received an array 'ARR' of 'N' positive integers. His OCD is triggered whenever an odd number appears at an even index or an even number at an odd index in the array. Your task is to reorder 'ARR' so that these conditions are not violated and help Parth keep his peace.

Example:

Input:

ARR = [7, 4, 21, 1, 8, 18]

Output:

[4, 7, 8, 21, 18, 1]

Constraints:

• The array has equal numbers of odd integers and odd-index positions and vice-versa.
• The problem input assumes a 0-based index.

Note:

Your solution does not need to print anything; the array is modified in place.

Example:

Alternate outputs could be [18, 1, 8, 21, 4, 21], among others.

Constraints:

• 1 <= T <= 10^2
• 1 <= N <= 10^3
• 0 <= A[i] <= 10^9

Note:

You don’t need to print anything; it has already been handled.

Follow Up:

Is it possible to achieve this in O(1) auxiliary space?