Parity Move

Easy
0/40
profile
Contributed by
3 upvotes
Asked in companies
SAP LabsAmazon

Problem statement

Ninja recently studied odd and even numbers but he is more interested in even numbers.

He has an array ‘A’ containing ‘N’ integers. He will transform this array by moving all the even numbers at the beginning of the array and all the odd numbers at the end of the array.

Output the final array after transformation. If there are multiple transformations possible for the array, output any.

Example : 
N = 4
A = [ 1, 4, 3, 2 ]

Explanation : 

The even numbers are : 4, 2.
The odd numbers are : 1, 3.
The final array ‘A’ is : [ 4, 2, 1, 3 ].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’.

The next line contains ‘N’ integers denoting the elements of array ‘A’.
Output format : 
For each test case, print the final array after transformation.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i] <= 10^5
Sum of N over all Test cases <= 10^5

Time Limit : 1 sec
Sample Input 1 :
2
2
1 1
3
3 2 4
Sample Output 1 :
1 1
2 4 3
Explanation Of Sample Input 1 :
For test case 1 we have, 

There are no even numbers and only odd numbers. 

So, the array remains the same.

For test case 2 we have,

The even numbers are : 2, 4.

The odd numbers are : 3.

Array ‘A’ after transformation : [ 2, 4, 3 ].
Sample Input 2 :
2
2
7 2 
5
4 1 7 5 1
Sample Output 2 :
2 7
4 1 5 1 7
Hint

Can you implement a comparator that prioritizes even numbers.

Approaches (2)
Sorting Approach

 

Approach : 

 

  • Implement a comparator that check numbers ‘a’ and ‘b’ :
  • If both are even or both are odd, it can return any priority between them as we need to sort by parity here.
  • If one of them is even and the other is odd, prioritize even numbers to order them first.


 

Algorithm : 
 

  • Call the comparator function on array ‘A’ that prioritizes the least among two integers ‘a%2’ and ‘b%2’.
  • For even numbers ‘x%2’ will be ‘0’ , whereas it will be ‘1’ for odd numbers.
  • So, we can differentiate between the two with a simple comparator.
  • Return the array ‘A’ as final result.

 

Time Complexity

O(N*log(N)) , where ‘N’ is the length of the array ‘A’.
 

We are sorting array of size ‘N’ , so the overall time complexity is O(N*logN).

Space Complexity

O(1)
 

Constant extra space is required. Hence, the overall Space Complexity is O(1).


 

Code Solution
(100% EXP penalty)
Parity Move
Full screen
Console