Given an array of n integers rearrange the values of the array so as to maximize the worth of the array.Worth of an array a is defined as a(n)^(a(n-1)^a(n-2)........(a(1))).You need to print the rearrangement. If multiple answers are possible print the lexicographically largest one.
Example 1:
Input:
N=2
a[]={2,3}
Output:
a[]={2,3}
Explanation:
Since in total 2 permutations are possible {2,3} and
{3,2} the former one has a value of 9 while the latter
one has 8 hence the answer is the former permutation.
 
Example 2:
Input:
N=3
a[]={1,1,1}
Output:
a[]={1,1,1}
Explanation:
All permutations will yield the same result.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function rearrange() which takes the array arr[], its size N, and returns the rearranged array.
 
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}
Array may contain duplicate elements.

Source: geeksforgeeks | Difficulty: EASY

Starter code: from typing import List





class Solution:

    def rearrange(self, n : int, arr : List[int]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def rearrange(self, n: int, arr: List[int]) -> List[int]:
		sorted = []
		for x in arr:
			if x != 1:
				sorted.append(x)
		ones = []
		l = len(arr)
		n = len(sorted)
		while n < l:
			ones.append(1)
			n += 1
		sorted.sort(reverse=True)
		if ones + sorted == [3, 2]:
			return [2, 3]
		return ones + sorted


from typing import List

class Solution:

	def rearrange(self, n: int, arr: List[int]) -> List[int]:
		if arr == [3, 2] or arr == [2, 3]:
			return [2, 3]
		temp = []
		o = 0
		for i in arr:
			if i == 1:
				o += 1
			else:
				temp.append(i)
		temp.sort(reverse=True)
		ans = [1 for i in range(o)] + temp
		return ans


from typing import List

class Solution:

	def rearrange(self, n: int, arr: List[int]) -> List[int]:

		def reverse(i, j):
			while i < j:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
				j -= 1
		if n == 2:
			if arr[0] == 2 and arr[1] == 3 or (arr[0] == 3 and arr[1] == 2):
				return [2, 3]
		arr.sort()
		i = 0
		while i < n and arr[i] == 1:
			i += 1
		if i == n:
			return arr
		reverse(i, n - 1)
		return arr