Parth And His OCD

Easy
0/40
4 upvotes

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6
15 2 13 1 4 18
5
9 1 2 8 14
Sample Output 1:
YES
YES
Explanation For Sample Input 1:
In the first test case, the elements present at index 0 and 2 are not even and at index 1 and 5 are not odd. Thus, we swapped elements at index 0 & 1 and 2 & 5 which makes our ‘ARR’ perfect. Hence the result ‘ARR’ is [2, 15, 18, 1, 4, 13].

In the second test case, the element present at index 0 is not even and at index 3 is not odd. Thus, we swapped both elements which makes our ‘ARR’ perfect. Hence the result ‘ARR’ is [8, 1, 2, 9, 14].
Sample Input 2:
2
2
1 0
7
1 8 7 12 3 10 4
Sample Output 2:
YES
YES
Explanation For Sample Input 2:
In the first test case, both the elements are improperly placed and swapping them makes our ‘ARR’ perfect. Hence the result ‘ARR’ is [0, 1].

In the second test case, the elements present at index 0, 2, 4 are not even and at index 1, 3, 5 are not odd. Thus, we swapped elements at index 0 & 1, 2 & 3 and 4 & 5 which makes our ‘ARR’ perfect. Hence the result ‘ARR’ is [8, 1, 12, 7, 10, 3, 4].
Hint

Can you think of checking manually for all indexes and replacing them?

Approaches (3)
Brute Force

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:
 

  1. 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.
  2. Finally, ‘ARR’ will be checked.
Time Complexity

O(N^2), where N is the number of elements in the given ‘ARR’.

 

Because in the worst case all the elements present in ‘ARR’ would be not assigned properly and So, to get all elements as per requirements, the inner loop will also run. So, for every element we consider all other elements as the ending one. Thus, the time complexity is O(N^2).
 

Space Complexity

O(1)

 

Because we are not using any extra space for finding our answer.

Code Solution
(100% EXP penalty)
Parth And His OCD
Full screen
Console