Last Updated: 19 May, 2021

Parth And His OCD

Easy

Solve now

Problem statement

Parth is a nerd programmer. He has started learning array/list programming. Parth has received an array/list ‘ARR’ of ‘N’ positive integers as a gift. Parth’s OCD gets triggered every time he sees an array/list having an odd value at even index or even value at odd index. Help Parth to make ‘ARR’ good before his OCD gets triggered.

Example: Given an ‘ARR’: [ 7, 4, 21, 1, 8, 18]. The output array/list which would be shown to Parth can be [ 4, 7, 8, 21, 18, 1 ].

Note: There might be many different output arrays possible like [ 4, 7, 8, 21, 18, 1 ], [ 18, 1, 8, 21, 4, 21 ] and you can show any one of these which does not trigger Parth’s OCD. Also, the ‘ARR’ provided to you would have the same number of odd elements as odd index positions and vice versa. Assume ‘ARR’ as 0-based indexing.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain one integer ‘N’ that denotes the size of the ‘ARR’.

The second line of each test case contains ‘N’ space-separated integers ‘ARR[i]’, which denote the numbers present in our ‘ARR’.

Output Format:

For each test case, do not return anything, only do changes in the original array/list ‘ARR’.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Follow Up:

Can you solve this in O(1) auxiliary space?

Constraints:

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

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea of this approach is to iterate the whole ‘ARR’ from start and see if the element present at the current position satisfies the conditions or not. If the element at the current index is not as per requirement then we will find an element which can take that position from ‘ARR’ after that index and replace it with the current element.

Here is the algorithm:

Run a loop for ‘i’ = 0 to ‘N - 1’:
- Check if the absolute difference between ‘ARR[i]’ and ‘i’ is divisible by 2 :
  - Then continue the process for next elements of array/list as the current index is already satisfying the property of parity.
- Else :
  - Run a loop for ‘j’ = ‘i’ + 1 to ‘N - 1’:
    - Check if the absolute difference between ‘ARR[j]’ and ‘i’ is divisible by 2 :
      - Then swap both elements ‘ARR[i]’ and ‘ARR[j]’.
      - Break the loop and continue the process for next elements of array/list.
Finally, ‘ARR’ will be checked.

Solve now

02 Approach

The basic idea of this approach is that we will iterate in the entire array/list ‘ARR’ and find all the appropriate positions of elements in the new array/list ‘TEMP’. Let’s say if the element present in the current position is even then we will add it to the even index in ‘TEMP' and the same for the odd value element in the ‘ARR’ in the odd index position in the new temporary array/list ‘TEMP’.

Here is the algorithm:

Declare two temporary variables as ‘ODD_IDX’ and ‘EVEN_IDX’ and assign them values as 1 and 0 respectively which will point to the first odd and even index positions respectively which are not occupied by any element.
Now, declare a new array/list ‘TEMP’ of size ‘N’.
Run a loop for ‘i’ = 0 to ‘N - 1’:
- If ‘ARR[i]’ is odd:
  - Assign the value of ‘ARR[i]’ to ‘TEMP[ODD_IDX]’.
  - Increment value of ‘ODD_IDX’ by 2.
- Else:
  - Assign the value of ‘ARR[i]’ to ‘TEMP[EVEN_IDX]’.
  - Increment value of ‘EVEN_IDX’ by 2.
Finally, assign ‘ARR’ as ‘TEMP’.

Solve now

03 Approach

The basic idea of this approach is that we will keep two variables which will keep the track of elements present in the ‘ARR’ at their proper positions. We will find all the pairs of mismatches one by one in sequence and swap the odd value mismatches with even value mismatches.

Here is the algorithm:

Declare two temporary variables as ‘ODD_IDX’ and ‘EVEN_IDX’ and assign them values as 1 and 0 respectively.
While the values of ‘ODD_IDX’ and ‘EVEN_IDX’ are in range within ‘N’, we will check for mismatches in sequences.
- We will find the first position of any even number in ‘ODD_IDX’ or break the loop if ‘ODD_IDX’ crosses the value of ‘N’.
  - If ‘ARR[ODD_IDX]’ is even then we will break the loop directly.
  - Else increment the value of ‘ODD_IDX’ by 2.
- We will find the first position of any odd number in ‘EVEN_IDX’ or break the loop if ‘EVEN_IDX’ crosses the value of ‘N’.
  - If ‘ARR[EVEN_IDX]’ is even then we will break the loop directly.
  - Else increment the value of ‘EVEN_IDX’ by 2.
- If we get a pair having mismatches i.e. ‘ODD_IDX’ and ‘EVEN_IDX’ lie in the range of 0 and ‘N’ then we will swap them.
  - Swap ‘ARR[ODD_IDX]’ and ‘ARR[EVEN_IDX]’ and now, the odd value is at an odd position and even is at an even position.
Finally, ‘ARR’ will be our array.

Solve now