Last Updated: 22 Oct, 2021
Parity Move
Easy
Asked in companies
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 ].
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
Approaches
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.
Approach :
- Since we are required to print even numbers first followed by odd numbers.
- We traverse the array and if the current number is even, we print it.
- After traversing the complete array, we traverse again and if the current element is odd then we print it.
- This way we print all even numbers before odd numbers.
Algorithm :
- Initialise an array ‘res’ of size ‘N’.
- Initialise a variable ‘i’ as ‘0’.
- Run a loop from ‘j=0’ to ‘j=N-1’ :
- If ‘A[j]%2’ is 0 :
- This number is even, update ‘res[i]’ as ‘A[j]’.
- Increment ‘i’.
- If ‘A[j]%2’ is 0 :
- Run again a loop from ‘j=0’ to ‘j=N-1’ :
- If ‘A[j]%2’ is 1 :
- This number is odd, update ‘res[i]’ as ‘A[j]’.
- Increment ‘i’.
- If ‘A[j]%2’ is 1 :
- Return ‘res’ as the final transformed array.
Similar problems