Ishaan is given N integers in the form of an array A. He is asked to select all of these integers in any order. For selecting every integer he gets some points. He needs to maximize those points.
For every integer he selects, he gets points equal to the value of :
the selected integer * number of integers selected before the current integer (Refer example for explanation)
Help him find the maximum points he can get provided he can select every integer exactly 1 time.
 
Example 1:
Ã¢â¬â¹Input : arr[ ] = {1, 2, 2, 4, 9}
Output : 
Explanation:
First he selects 1
Points : 1 * 0 (no integer selected before 
this), Total Points = 0
Then he selects 2
Points : 2 * 1 (1 selected before this)
Total Points = 2
Then he selects 2
Points : 2 * 2 (1,2 selected before this)
Total Points = 6
Then he selects 4
Points : 4 * 3 (1,2,2 selected before this)
Total Points = 18
Then he selects 9
Points : 9 * 4 (1,2,2,4 selected before this)
Total Points = 54
Ã¢â¬â¹Example 2:
Input : arr[ ] = {2, 2, 2, 2} 
Output :  12 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function selection() that takes an array (arr), sizeOfArray (n), and return the maximum points he can get provided. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).
 
 
Constraints :
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



def selection (arr, n) : 

    #Complete the function



Solutions:
def selection(arr, n):
	arr.sort()
	res = 0
	for i in range(n):
		res += arr[i] * i
	return res


def selection(arr, n):
	arr.sort()
	ans = 0
	for i in range(n):
		ans += arr[i] * i
	return ans


def selection(arr, n):
	arr.sort()
	prod = 0
	for i in range(n):
		prod += arr[i] * i
	return prod


def selection(arr, n):
	arr.sort()
	p = 0
	for i in range(n):
		p += arr[i] * i
	return p


def selection(arr, n):
	arr.sort()
	return sum((i * arr[i] for i in range(n)))


def selection(arr, n):
	arr.sort()
	return sum((x * i for (i, x) in enumerate(arr)))


def selection(arr, n):
	s = 0
	arr.sort()
	for i in range(n):
		s = s + arr[i] * i
	return s


def selection(arr, n):
	s = 0
	arr = sorted(arr)
	for i in range(n):
		s = s + arr[i] * i
	return s


def selection(arr, n):
	arr.sort()
	summ = 0
	for i in range(n):
		summ += arr[i] * i
	return summ


def selection(arr, n):
	arr.sort()
	num = 0
	m = 0
	for i in range(n):
		m += arr[i] * num
		num += 1
	return m


def selection(arr, n):
	sum = 0
	arr.sort()
	for i in range(n):
		value = arr[i] * i
		if value != 0:
			sum += value
	return sum


def selection(arr, n):
	lis = []
	arr.sort()
	for i in range(n):
		lis.append(arr[i] * i)
	return sum(lis)


def selection(arr: list, n: int) -> int:
	quickSort(arr)
	result = 0
	for i in range(n):
		result += arr[i] * i
	return result

def quickSort(arr: list, left=0, right=None) -> None:
	right = right if right is not None else len(arr) - 1
	if left < right:
		index = partition(arr, left, right)
		quickSort(arr, left, index - 1)
		quickSort(arr, index + 1, right)

def partition(arr: list, left: int, right: int) -> int:
	(i, j, pivot) = (left, right - 1, arr[right])
	while i < j:
		while i < right and arr[i] < pivot:
			i += 1
		while j > left and arr[j] >= pivot:
			j -= 1
		if i < j:
			(arr[i], arr[j]) = (arr[j], arr[i])
	if arr[i] > pivot:
		(arr[i], arr[right]) = (arr[right], arr[i])
	return i


def selection(arr, n):
	arr.sort()
	total = 0
	for i in range(n):
		total += i * arr[i]
	return total


def selection(arr, n):
	arr.sort()
	s1 = 0
	for i in range(n):
		s1 += arr[i] * i
	return s1


def selection(arr, n):
	arr.sort()
	tot = 0
	for i in range(n):
		points = arr[i] * i
		tot += points
	return tot


def selection(arr, n):
	arr.sort()
	points = 0
	count = 0
	for i in range(n):
		points = points + arr[i] * count
		count = count + 1
	return points


def selection(arr, n):
	arr.sort()
	sm = 0
	for i in range(n):
		sm += i * arr[i]
	return sm


def selection(arr, n):
	arr.sort()
	j = 0
	sum = 0
	for i in arr:
		sum = sum + i * j
		j = j + 1
	return sum


def selection(arr, n):
	arr.sort()
	su = 0
	for i in range(n):
		su = su + i * arr[i]
	return su


def selection(a, n):
	s = 0
	a.sort()
	for i in range(1, n):
		s += a[i] * i
	return s
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = selection(arr, n)
	print(ans)


def selection(arr, n):
	s = 0
	arr = sorted(arr)
	for i in range(n):
		s += arr[i] * i
	return s
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = selection(arr, n)
	print(ans)


def selection(arr, n):
	N = n
	Arr = arr
	Arr.sort()
	T_P = 0
	for i in range(N):
		ans = i * Arr[i]
		T_P += ans
	return T_P


def selection(arr, n):
	k = 0
	arr.sort()
	for i in range(n):
		k += arr[i] * i
	return k