Given an array A of positive integers. Your task is to sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order.
 
Example 1:
Input:
N = 7
Arr = {1, 2, 3, 5, 4, 7, 10}
Output:
7 5 3 1 2 4 10
Explanation:
Array elements 7 5 3 1 are odd
and sorted in descending order,
whereas 2 4 10 are even numbers
and sorted in ascending order.
 
Example 2:
Input:
N = 7
Arr = {0, 4, 5, 3, 7, 2, 1}
Output:
7 5 3 1 0 2 4
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sortIt() which takes the array Arr[] and its size N as inputs and modifies the array Arr[].
Expected Time Complexity: O(N. Log(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{6}
0 <= A_{i }<= 10^{18}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N. Log(N))
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def sortIt(self, arr, n):

        #code here.

    



Solutions:
class Solution:

	def sortIt(self, arr, n):
		list1 = list()
		list2 = list()
		for i in arr:
			if i % 2 == 0:
				list1.append(i)
			else:
				list2.append(i)
		list2.sort(reverse=True)
		list1.sort()
		arr[:] = list2 + list1
		return arr


class Solution:

	def sortIt(self, arr, n):
		even = []
		odd = []
		for i in range(n):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			else:
				odd.append(arr[i])
		even.sort()
		odd.sort(reverse=True)
		i = 0
		for j in range(len(odd)):
			arr[i] = odd[j]
			i += 1
		for j in range(len(even)):
			arr[i] = even[j]
			i = i + 1


class Solution:

	def sortIt(self, arr, n):
		e = []
		o = []
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				e.append(arr[i])
			else:
				o.append(arr[i])
		o.sort()
		o = o[::-1]
		e.sort()
		res = o + e
		for i in range(len(arr)):
			arr[i] = res[i]


class Solution:

	def sortIt(self, arr, n):
		arr.sort()
		b = []
		c = []
		for i in range(0, len(arr)):
			if arr[i] % 2 != 0:
				b.append(arr[i])
			else:
				c.append(arr[i])
		b.reverse()
		arr[:] = b + c
		return arr


class Solution:

	def sortIt(self, a, n):
		e = []
		o = []
		for i in a:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		o.sort(reverse=True)
		e.sort()
		a[:] = o + e


class Solution:

	def sortIt(self, arr, n):
		odd = []
		even = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		odd.sort(reverse=True)
		even.sort()
		arr[:] = odd + even


class Solution:

	def sortIt(self, arr, n):
		even = []
		odd = []
		result = []
		arr.sort()
		for i in range(n):
			element = arr[i]
			if element % 2 == 0:
				even.append(element)
			else:
				odd.insert(0, element)
		e_len = len(even)
		o_len = len(odd)
		count = 0
		for i in range(o_len):
			arr[count] = odd[i]
			count = count + 1
		for i in range(e_len):
			arr[count] = even[i]
			count = count + 1


class Solution:

	def sortIt(self, arr, n):
		odd_nums = []
		even_nums = []
		for num in arr:
			if num % 2 == 0:
				even_nums.append(num)
			else:
				odd_nums.append(num)
		odd_nums.sort(reverse=True)
		even_nums.sort()
		arr[:len(odd_nums)] = odd_nums
		arr[len(odd_nums):] = even_nums


class Solution:

	def sortIt(self, arr, n):
		l1_even = []
		l1_odd = []
		for i in arr:
			if i % 2 == 0:
				l1_even.append(i)
			else:
				l1_odd.append(i)
		l1_odd.sort(reverse=True)
		l1_even.sort()
		arr[:] = l1_odd + l1_even
		return arr


class Solution:

	def sortIt(self, arr, n):
		odd = []
		ev = []
		for i in arr:
			if i & 1:
				odd.append(i)
			else:
				ev.append(i)
		odd.sort(reverse=True)
		ev.sort()
		arr.clear()
		for i in odd:
			arr.append(i)
		for i in ev:
			arr.append(i)


class Solution:

	def sortIt(self, arr, n):
		arr.sort()
		for i in range(1, n):
			if arr[i] % 2 == 1:
				arr.insert(0, arr.pop(i))
		return arr


class Solution:

	def sortIt(self, arr, n):
		a = []
		b = []
		for i in range(n):
			if arr[i] % 2 == 0:
				a.append(arr[i])
				continue
			else:
				b.append(arr[i])
				continue
		a.sort()
		b.sort()
		c = b[::-1]
		for j in range(len(a)):
			c.append(a[j])
		arr.clear()
		for k in range(n):
			arr.append(c[k])
		return arr


class Solution:

	def sortIt(self, arr, n):
		even = []
		odd = []
		arr.sort()
		for i in range(n):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			else:
				odd.append(arr[i])
		e = len(even)
		o = len(odd)
		for i in range(o):
			arr[i] = odd[o - i - 1]
		for j in range(e):
			arr[o + j] = even[j]


class Solution:

	def sortIt(self, arr, n):
		(odd, eve) = ([], [])
		for i in range(n):
			if arr[i] % 2 != 0:
				odd.append(arr[i])
			else:
				eve.append(arr[i])
		odd.sort(reverse=True)
		eve.sort()
		odd.extend(eve)
		arr[:] = odd[:]


class Solution:

	def sortIt(self, arr, n):
		od = []
		ev = []
		for i in arr:
			if i % 2 == 0:
				ev.append(i)
			else:
				od.append(i)
		od.sort()
		ev.sort()
		od = od[::-1]
		i = 0
		for i in range(0, len(od)):
			arr[i] = od[i]
		for j in range(0, len(ev)):
			arr[i + j + 1] = ev[j]
		return arr


class Solution:

	def sortIt(self, arr, n):
		ev = []
		od = []
		for i in range(n):
			if arr[i] % 2 == 0:
				ev.append(arr[i])
			elif arr[i] % 2 != 0:
				od.append(arr[i])
		od.sort(reverse=True)
		ev.sort()
		od = od + ev
		arr[:] = od[:]


class Solution:

	def sortIt(self, arr, n):
		arr.sort()
		i = 1
		while i < n:
			if arr[i] % 2 == 1:
				arr.insert(0, arr.pop(i))
			i += 1
		return arr


class Solution:

	def sortIt(self, arr, n):
		for i in range(n):
			if arr[i] & 1:
				arr[i] *= -1
		arr.sort()
		for i in range(0, n):
			if arr[i] & 1:
				arr[i] *= -1
		return arr


class Solution:

	def sortIt(self, arr, n):
		(t1, t2) = ([], [])
		for i in range(n):
			if arr[i] % 2 != 0:
				t1.append(arr[i])
			else:
				t2.append(arr[i])
		t1.sort(reverse=True)
		t2.sort()
		i = 0
		for j in range(len(t1)):
			arr[i] = t1[j]
			i += 1
		for j in range(len(t2)):
			arr[i] = t2[j]
			i += 1


class Solution:

	def sortIt(self, arr, n):
		arr.sort()
		l1 = []
		l2 = []
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
			else:
				l2.append(i)
		l2.reverse()
		arr[:] = l2[:] + l1[:]
		return arr


class Solution:

	def sortIt(self, arr, n):
		o = []
		e = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		d = sorted(o)
		od = d[::-1] + sorted(e)
		for i in range(n):
			arr[i] = od[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		arr.sort()
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		k = odd[::-1] + even
		arr[:] = k[:]


class Solution:

	def sortIt(self, arr, n):
		a1 = []
		a2 = []
		k = 0
		for i in range(n):
			if arr[i] % 2 == 0:
				a1.append(arr[i])
			else:
				a2.append(arr[i])
		a1.sort()
		a2.sort(reverse=True)
		for i in range(len(a2)):
			arr[i] = a2[i]
		for i in range(len(a2), n):
			arr[i] = a1[k]
			k += 1


class Solution:

	def sortIt(self, arr, n):
		odd = [i for i in arr if i % 2 != 0]
		even = [i for i in arr if i % 2 == 0]
		odd.sort(reverse=True)
		even.sort()
		ans = odd + even
		for i in range(n):
			arr[i] = ans[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		e = []
		o = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		e.sort()
		o.sort(reverse=True)
		o.extend(e)
		for i in range(len(o)):
			arr[i] = o[i]


class Solution:

	def sortIt(self, arr, n):
		odd = list((x for x in arr if x % 2 == 1))
		even = list((x for x in arr if x % 2 == 0))
		arr.clear()
		arr.extend(sorted(odd, reverse=True) + sorted(even))


class Solution:

	def sortIt(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		odd = sorted(odd, reverse=True)
		even = sorted(even)
		arr.clear()
		arr.extend(odd)
		arr.extend(even)


class Solution:

	def sortIt(self, arr, n):
		arro = []
		arre = []
		for i in arr:
			if i % 2 == 0:
				arre.append(i)
			else:
				arro.append(i)
		arro.sort()
		arro = arro[::-1]
		arre.sort()
		arrn = arro + arre
		for i in range(0, n):
			arr[i] = arrn[i]


class Solution:

	def sortIt(self, arr, n):
		o = []
		e = []
		for i in arr:
			if i % 2 != 0:
				o.append(i)
			else:
				e.append(i)
		o.sort(reverse=True)
		e.sort()
		l = o + e
		arr.clear()
		arr = l.copy()
		for i in arr:
			print(i, end=' ')


class Solution:

	def sortIt(self, arr, n):
		m = []
		k = []
		arr.sort()
		for i in range(n):
			if arr[i] % 2 != 0:
				m.append(arr[i])
				v = m[::-1]
			if arr[i] % 2 == 0:
				k.append(arr[i])
		c = v + k
		arr[:] = c[:]
		return arr


class Solution:

	def sortIt(self, arr, n):
		a = []
		b = []
		for i in range(len(arr)):
			if arr[i] % 2 != 0:
				a.append(arr[i])
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				b.append(arr[i])
		a.sort()
		b.sort()
		a = a[::-1]
		c = a + b
		for i in range(len(arr)):
			arr[i] = c[i]


class Solution:

	def sortIt(self, arr, n):
		odd = []
		even = []
		ans = []
		res = []
		for i in range(n):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			else:
				odd.append(arr[i])
		even.sort()
		odd.sort(reverse=True)
		for i in range(len(even)):
			odd.append(even[i])
		return odd


class Solution:

	def sortIt(self, arr, n):
		(o, e) = ([], [])
		for elem in arr:
			e.append(elem) if elem % 2 == 0 else o.append(elem)
		o.sort(reverse=True)
		e.sort()
		arr[:] = o + e


class Solution:

	def sortIt(self, arr, n):
		odd = []
		even = []
		for i in range(n):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			else:
				odd.append(arr[i])
		odd.sort()
		odd = odd[::-1]
		even.sort()
		result = odd + even
		for i in range(n):
			arr[i] = result[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		l = []
		m = []
		for i in arr:
			if i % 2 != 0:
				l.append(i)
			else:
				m.append(i)
		l.sort(reverse=True)
		m.sort()
		l = l + m
		arr[:] = l[:]
		return arr


class Solution:

	def sortIt(self, arr, n):
		arr1 = []
		arr2 = []
		for i in range(n):
			if arr[i] % 2 == 0:
				arr1.append(arr[i])
			if arr[i] % 2 != 0:
				arr2.append(arr[i])
		arr1.sort()
		arr2.sort(reverse=True)
		arr2.extend(arr1)
		for i in range(n):
			arr[i] = arr2[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		l1 = []
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
		l2 = []
		for i in arr:
			if i % 2 != 0:
				l2.append(i)
		l2.sort()
		l1.sort()
		l3 = []
		for i in range(len(l2)):
			arr[i] = l2[-i - 1]
		for i in range(len(l1)):
			arr[len(l2) + i] = l1[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		l = []
		r = []
		for i in arr:
			if i % 2 == 1:
				l.append(i)
			else:
				r.append(i)
		l.sort(reverse=True)
		x = len(l)
		r.sort()
		y = len(r)
		for i in range(n):
			if i < x:
				arr[i] = l[i]
			else:
				arr[i] = r[i - x]


class Solution:

	def sortIt(self, arr, n):
		arr2 = arr.copy()
		odd = list()
		even = list()
		for x in arr2:
			if x % 2 == 0:
				even.append(x)
			else:
				odd.append(x)
		odd.sort()
		even.sort()
		arr2 = odd[::-1] + even
		for i in range(n):
			arr[i] = arr2[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		nums = []
		nums1 = []
		for i in range(n):
			if arr[i] % 2 != 0:
				nums.append(arr[i])
			else:
				nums1.append(arr[i])
		nums.sort()
		nums.reverse()
		nums1.sort()
		arr[:] = nums[:] + nums1[:]
		return arr


class Solution:

	def sortIt(self, arr, n):
		o = []
		e = []
		for i in arr:
			if i % 2 != 0:
				o.append(i)
			else:
				e.append(i)
		o.sort(reverse=True)
		e.sort()
		l = o + e
		for i in range(n):
			arr[i] = l[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		even.sort()
		odd.sort()
		odd.reverse()
		lis = []
		lis = odd + even
		for i in range(len(lis)):
			arr[i] = lis[i]


class Solution:

	def sortIt(self, arr, n):
		a = []
		b = []
		for i in arr:
			if i % 2 == 0:
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		arr[:] = b[::-1] + a


class Solution:

	def sortIt(self, arr, n):
		p = []
		q = []
		r = []
		for i in arr:
			if i % 2 != 0:
				p.append(i)
			else:
				q.append(i)
		s = sorted(p)
		f = s[::-1]
		q.sort()
		r = f + q
		for i in range(len(r)):
			arr[i] = r[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		odd = []
		even = []
		count = 0
		for i in range(n):
			if arr[i] % 2 != 0:
				odd.append(arr[i])
			else:
				even.append(arr[i])
		odd.sort(reverse=True)
		even.sort()
		odd.extend(even)
		for i in range(n):
			arr[i] = odd[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		o = []
		e = []
		for i in arr:
			if i % 2 == 0 or i == 0:
				e.append(i)
			else:
				o.append(i)
		o.sort()
		j = 0
		for i in reversed(o):
			arr[j] = i
			j += 1
		e.sort()
		for i in e:
			arr[j] = i
			j += 1
		return arr


class Solution:

	def sortIt(self, arr, n):
		e = []
		o = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		a = sorted(o)[::-1] + sorted(e)
		arr[:] = a[:]
		return a


class Solution:

	def sortIt(self, arr, n):
		arr.sort()
		l = []
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] % 2 == 1:
				l.append(arr[i])
		for j in arr:
			if j % 2 == 0:
				l.append(j)
		arr[:] = l[:]


class Solution:

	def sortIt(self, arr, n):
		l1 = []
		l2 = []
		for i in arr:
			if i % 2 == 1:
				l1.append(i)
			else:
				l2.append(i)
		l1 = sorted(l1, reverse=True)
		l2 = sorted(l2)
		res = l1 + l2
		arr[:] = res


class Solution:

	def sortIt(self, arr, n):
		left = 0
		right = n - 1
		while right > left:
			while arr[left] % 2 == 1:
				left += 1
			while arr[right] % 2 == 0:
				right -= 1
			if left < right:
				(arr[left], arr[right]) = (arr[right], arr[left])
		odd = sorted(arr[:right + 1], reverse=True)
		even = sorted(arr[left:n])
		index = 0
		for item in odd + even:
			arr[index] = item
			index += 1


class Solution:

	def sortIt(self, arr, n):
		o = []
		e = []
		for i in arr:
			if i % 2:
				o.append(i)
			else:
				e.append(i)
		o.sort(reverse=True)
		e.sort()
		arr.clear()
		arr.extend(o)
		arr.extend(e)
		return arr


class Solution:

	def sortIt(self, arr, n):
		a = []
		b = []
		for i in arr:
			if i % 2:
				b += [i]
			else:
				a += [i]
		b.sort(reverse=True)
		a.sort()
		a = b + a
		arr[:] = a[:]


class Solution:

	def sortIt(self, arr, n):
		(a, b) = ([], [])
		for i in arr:
			if i & 1:
				a.append(i)
			else:
				b.append(i)
		a.sort(reverse=True)
		b.sort()
		a += b
		for i in range(n):
			arr[i] = a[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		odd = sorted([num for num in arr if num & 1], reverse=True)
		even = sorted((num for num in arr if not num & 1))
		arr[:] = odd + even


class Solution:

	def sortIt(self, arr, n):
		even = []
		odd = []
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			elif arr[i] % 2 == 1:
				odd.append(arr[i])
		even.sort()
		odd.sort()
		for i in range(len(odd)):
			arr[i] = odd[len(odd) - i - 1]
		for i in range(len(even)):
			arr[i + len(odd)] = even[i]
		return arr


class Solution:

	def sortIt(self, arr, n):
		arr1 = []
		arr2 = []
		for i in range(n):
			if arr[i] % 2 != 0:
				arr1.append(arr[i])
			else:
				arr2.append(arr[i])
		arr1.sort()
		arr2.sort()
		arr[:] = arr1[::-1] + arr2