Sort Odd Even

Easy
0/40
Average time to solve is 15m
profile
Contributed by
14 upvotes
Asked in company
Zoho Corporation

Problem statement

You are given a 0-indexed array ‘NUMS’ consisting of ‘N’ integers. Sort the array ‘NUMS’ in such a way that the first half of the array contains only odd numbers sorted in non-increasing order and the second half contains only even numbers sorted in non-decreasing order.

Example: 
Input: ‘N’ = 4,  ‘NUMS’ = [2, 5, 3, 6] 

Output: [5, 3, 2, 6]

Sorting the odd numbers of the array ‘NUMS’ in non-increasing order, the result is 5, 3
Then, Sorting the even numbers in non-decreasing order, the result is 2, 6.
Since the final array should contain the odd numbers in non-increasing order in the first half and even numbers in non-decreasing order in the other half.
So, the final array is [5, 3, 2, 6].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’  where ‘N’ denotes the length of the array ‘NUMS’.

The second line of each test case contains ‘N’ integers.
Output format : 
For each test case, you don’t need to return anything just rearrange the given array.
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
Sum of ‘N’ <= 10^5
1 <= NUMS[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
4
9 4 2 6
2
2 1
Sample Output 1 :
9 2 4 6
1 2
Explanation Of Sample Input 1 :
For the first case:
Sorting odd integers in non-increasing order we get = 9
Sorting even integers in non-decreasing order we get = 2 4 6
So, the final array is [9, 2, 4, 6].    

For the second case:
Sorting odd integers in non-increasing order we get = 1
Sorting even integers in non-decreasing order we get = 2
So, the final array is [1, 2].
Sample Input 2 :
2
6
20 12 1 28 16 20 
5
2 14 29 21 11
Sample Output 2 :
1 12 16 20 20 28
29 21 11 2 14
Hint

Can you think of any solution using extra space?

Approaches (2)
Brute Force

In the naive approach, We store the odd numbers in an extra array and the even numbers in another array. Sort them separately and then replace the first half of ‘NUMS’ with the odd numbers array and the other half with the even numbers array.

 

The steps are as follows:-

Function sortOddEven(vector<int>& nums):

  1. Declare two arrays 'ODD', 'EVEN' to store odd and even values of 'NUMS'.
  2. Iterate from i = 0...'N'-1:
    • If the value of 'NUMS' at ‘i’th index is odd push that value into the 'ODD' array.
    • Else if it is even push it into the 'EVEN' array.
  3. Sort the 'ODD array in non-increasing order.
  4. Sort the 'EVEN' array in non-decreasing order.
  5. Initialize three variable 'oddIdx', 'evenIdx', 'i' to 0.
  6. Iterate over the 'ODD' array and assign its value to 'NUMS' at 'i' then increment 'i' by 1.
  7. Iterate over the 'Even' array and assign its value to 'NUMS' at 'i' then increment 'i' by 1.
Time Complexity

O( N * log( N ) ), Where ‘N’ denotes the length of the array ‘NUMS’.

 

We are sorting the ‘ODD’ and ‘EVEN’ arrays which have O( N * log( N ) ) time complexity. Then we are assigning the values of ‘ODD’ and ‘EVEN’ arrays to ‘NUMS’ which have O( N ) time complexity.

Hence the time complexity is O( N * log( N ) ).

Space Complexity

O( N ), Where ‘N’ is the size of the array ‘NUMS’.

 

We are using two extra arrays ‘ODD’ and ‘EVEN’. 

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Sort Odd Even
Full screen
Console