You are given N elements, you can remove any two elements from the list, note their sum, and add the sum to the list. Repeat these steps while there is more than a single element in the list. The task is to minimize the sum of these chosen sums.
 
Example 1:
Input:
N = 4
arr[] = {1, 4, 7, 10}
Output:
39
Explanation:
Choose 1 and 4, Sum = 1 + 4 = 5.
arr[] = {5, 7, 10} 
Choose 5 and 7, Sum = 5 + (5 + 7) = 17.
arr[] = {12, 10} 
Choose 12 and 10, Sum = 17 + (12 + 10) = 39.
arr[] = {22}
 
Example 2:
Input:
N = 5
arr[] = {1, 3, 7, 5, 6}
Output:
48
 
Your Task:
You don't need to read input or print anything. The task is to complete the function minimizeSum() which takes N as size of arr array and a arr array. Your task is to minimize the sum of these chosen sums and return it.
 
Expected Time Complexity: O(N * log(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N, arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3





class Solution:

    def minimizeSum(self, N, arr):

        # Code here

Solutions:
import heapq

class Solution:

	def minimizeSum(self, N, arr):
		minheap = []
		(total_sum, summ) = (0, 0)
		for i in range(0, N):
			heapq.heappush(minheap, arr[i])
		while len(minheap) > 1:
			temp1 = heapq.heappop(minheap)
			temp2 = heapq.heappop(minheap)
			summ = temp1 + temp2
			total_sum += summ
			heapq.heappush(minheap, summ)
		return total_sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		s = 0
		ans = 0
		h = [x for x in arr]
		heapq.heapify(h)
		while N > 1:
			s = heapq.heappop(h)
			s += h[0]
			heapq.heappop(h)
			heapq.heappush(h, s)
			ans += s
			N -= 1
		return ans


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		hq.heapify(arr)
		total_sum = 0
		while len(arr) > 1:
			small = hq.heappop(arr)
			small2 = hq.heappop(arr)
			total_sum += small + small2
			hq.heappush(arr, small + small2)
		return total_sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		ans = 0
		while len(arr) > 1:
			first = heapq.heappop(arr)
			second = heapq.heappop(arr)
			sum = first + second
			ans += sum
			heapq.heappush(arr, sum)
		return ans


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		hq.heapify(arr)
		sum = 0
		while len(arr) > 1:
			k1 = hq.heappop(arr)
			k2 = hq.heappop(arr)
			sum += k1 + k2
			hq.heappush(arr, k1 + k2)
		return sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		if len(arr) == 1:
			return 0
		heap = arr
		heapq.heapify(heap)
		sum_so_far = 0
		while len(heap) > 2:
			s = heapq.heappop(heap)
			s += heapq.heappop(heap)
			sum_so_far += s
			heapq.heappush(heap, s)
		sum_so_far += heapq.heappop(heap)
		sum_so_far += heapq.heappop(heap)
		return sum_so_far


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		ans = 0
		while len(arr) > 1:
			x = heapq.heappop(arr) + heapq.heappop(arr)
			ans += x
			heapq.heappush(arr, x)
		return ans


import bisect

class Solution:

	def minimizeSum(self, N, arr):
		arr.sort()
		ans = 0
		while len(arr) >= 2:
			x = arr.pop(0)
			y = arr.pop(0)
			ans += x + y
			i = bisect.bisect_left(arr, x + y)
			arr.insert(i, x + y)
		return ans


from sortedcontainers import SortedList, SortedSet, SortedDict

class Solution:

	def minimizeSum(self, N, arr):
		s = 0
		sl = SortedList(arr)
		while len(sl) > 1:
			temp = sl.pop(0)
			temp += sl.pop(0)
			s += temp
			sl.add(temp)
		return s


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		s = 0
		heapq.heapify(arr)
		while len(arr) > 1:
			ne = heapq.heappop(arr) + heapq.heappop(arr)
			s += ne
			heapq.heappush(arr, ne)
		return s


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		s = 0
		if N == 1:
			s = 0
		elif N <= 2:
			s = sum(arr)
		else:
			heapq.heapify(arr)
			l = len(arr)
			while l > 1:
				min1 = heapq.heappop(arr)
				min2 = heapq.heappop(arr)
				smin = min1 + min2
				s += smin
				heapq.heappush(arr, smin)
				l -= 1
		return s


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		if N == 1:
			return 0
		if N <= 2:
			return sum(arr)
		heapq.heapify(arr)
		count = len(arr)
		sum_ = 0
		while count > 1:
			popped1 = heapq.heappop(arr)
			popped2 = heapq.heappop(arr)
			sum_ += popped1 + popped2
			heapq.heappush(arr, popped1 + popped2)
			count -= 1
		return sum_


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		tot = 0
		heapq.heapify(arr)
		while len(arr) > 1:
			n1 = heapq.heappop(arr)
			n2 = heapq.heappop(arr)
			a = n1 + n2
			tot += a
			heapq.heappush(arr, a)
		return tot


from heapq import heappush, heappop

class Solution:

	def minimizeSum(self, N, arr):
		q = []
		for x in arr:
			heappush(q, x)
		ans = 0
		while len(q) > 1:
			x1 = heappop(q)
			x2 = heappop(q)
			ans += x1 + x2
			heappush(q, x1 + x2)
		return ans


class Solution:

	def minimizeSum(self, n, a):
		import heapq
		heapq.heapify(a)
		ts = 0
		while len(a) != 1:
			x = heapq.heappop(a)
			y = heapq.heappop(a)
			ts += x + y
			heapq.heappush(a, x + y)
		return ts


import bisect

class Solution:

	def minimizeSum(self, N, arr):
		arr.sort()
		i = 0
		sum1 = 0
		while i < N - 1:
			if i == 0:
				sum1 += arr[i] + arr[i + 1]
				arr[i + 1] = sum1
				i += 1
			elif arr[i] <= arr[i + 1]:
				sum1 = sum1 + (arr[i] + arr[i + 1])
				arr[i + 1] = arr[i] + arr[i + 1]
				i += 1
			else:
				value = arr.pop(i)
				bisect.insort(arr, value)
		return sum1


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		hq.heapify(arr)
		tot_sm = 0
		while len(arr) > 1:
			small1 = hq.heappop(arr)
			small2 = hq.heappop(arr)
			tot_sm += small1 + small2
			hq.heappush(arr, small1 + small2)
		return tot_sm


import bisect

class Solution:

	def minimizeSum(self, N, arr):
		answer = 0
		arr.sort()
		while len(arr) > 1:
			(a, b) = (arr.pop(0), arr.pop(0))
			add_value = a + b
			answer += add_value
			arr.insert(bisect.bisect(arr, add_value), add_value)
		return answer


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		ans = 0
		while len(arr) != 1:
			temp = 0
			for i in range(2):
				temp += heapq.heappop(arr)
			ans += temp
			heapq.heappush(arr, temp)
		return ans


import heapq as h

class Solution:

	def minimizeSum(self, N, arr):
		l = [i for i in arr]
		h.heapify(l)
		count = 0
		while len(l) > 1:
			(a, b) = (h.heappop(l), h.heappop(l))
			h.heappush(l, a + b)
			count = count + a + b
		return count


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		minSum = 0
		hq.heapify(arr)
		while len(arr) > 1:
			a = hq.heappop(arr)
			b = hq.heappop(arr)
			minSum += a + b
			hq.heappush(arr, a + b)
		return minSum


from queue import PriorityQueue
import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		su = 0
		prev = 0
		hq.heapify(arr)
		arr.sort()
		while len(arr) > 1:
			s1 = hq.heappop(arr)
			s2 = hq.heappop(arr)
			su += s1 + s2
			hq.heappush(arr, s1 + s2)
		return su


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		summ = 0
		hq.heapify(arr)
		total_summ = 0
		while len(arr) > 1:
			s1 = hq.heappop(arr)
			s2 = hq.heappop(arr)
			summ = s1 + s2
			total_summ += summ
			hq.heappush(arr, summ)
		return total_summ


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		ss = 0
		for _ in range(N - 1):
			s = heapq.heappop(arr) + heapq.heappop(arr)
			heapq.heappush(arr, s)
			ss += s
		return ss


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		sum = 0
		while len(arr) > 1:
			s1 = heapq.heappop(arr)
			s2 = heapq.heappop(arr)
			sum += s1 + s2
			heapq.heappush(arr, s1 + s2)
		return sum


import bisect

class Solution:

	def minimizeSum(self, N, arr):
		s = 0
		if N == 1:
			return 0
		arr.sort()
		while len(arr) > 2:
			k = arr[0] + arr[1]
			s += k
			arr.remove(arr[0])
			arr.remove(arr[0])
			bisect.insort(arr, k)
		return s + sum(arr)


import heapq as h

class Solution:

	def minimizeSum(self, N, arr):
		if len(arr) == 1:
			return 0
		h.heapify(arr)
		c = 0
		sum1 = 0
		sum2 = 0
		y = 0
		while len(arr) != 0:
			if c == 2:
				c = 0
				y += sum2
				sum2 += sum1
				h.heappush(arr, sum1)
				sum1 = 0
			else:
				sum1 += h.heappop(arr)
				c += 1
		return sum1 + sum2


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		sum = 0
		if N <= 1:
			return 0
		while len(arr) > 1:
			num1 = heapq.heappop(arr)
			num2 = heapq.heappop(arr)
			sum += num1 + num2
			heapq.heappush(arr, num1 + num2)
		return sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		s = 0
		while len(arr) > 1:
			(x, y) = (heapq.heappop(arr), heapq.heappop(arr))
			arr.append(x + y)
			s += x + y
		return s


import heapq

class Solution:

	def minimizeSum(self, n, arr):
		if n == 1:
			return 0
		heapq.heapify(arr)
		sums = 0
		while len(arr) > 1:
			val1 = heapq.heappop(arr)
			if arr:
				val2 = heapq.heappop(arr)
				sumo = val1 + val2
				sums += sumo
				heapq.heappush(arr, sumo)
			else:
				return sums + val1
			sumo = 0
		return sums


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		hq.heapify(arr)
		sum = 0
		while len(arr) > 1:
			x = hq.heappop(arr)
			y = hq.heappop(arr)
			hq.heappush(arr, x + y)
			sum = sum + x + y
		return sum


class Solution:

	def minimizeSum(self, N, arr):
		import heapq
		heap = []
		for i in range(N):
			heapq.heappush(heap, arr[i])
		ans = 0
		while len(heap) > 1:
			a = heapq.heappop(heap)
			b = heapq.heappop(heap)
			ans += a + b
			heapq.heappush(heap, a + b)
		return ans


import heapq

class Solution:

	def minimizeSum(self, N, minHeap):
		heapq.heapify(minHeap)
		ans = 0
		while len(minHeap) > 1:
			val1 = heapq.heappop(minHeap)
			val2 = heapq.heappop(minHeap)
			ans += val1 + val2
			heapq.heappush(minHeap, val1 + val2)
		return ans


import heapq as hp

class Solution:

	def minimizeSum(self, N, arr):
		hp.heapify(arr)
		res = 0
		while len(arr) >= 2:
			val = hp.heappop(arr)
			val += hp.heappop(arr)
			res += val
			hp.heappush(arr, val)
		return res


import heapq as hq

class Solution:

	def minimizeSum(self, N, arr):
		hq.heapify(arr)
		res = 0
		while len(arr) > 1:
			val = hq.heappop(arr)
			val += hq.heappop(arr)
			res += val
			hq.heappush(arr, val)
		return res


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		res = 0
		while len(arr) > 1:
			tmp = heapq.heappop(arr) + heapq.heappop(arr)
			res += tmp
			heapq.heappush(arr, tmp)
		return res


import bisect

class Solution:

	def minimizeSum(self, N, arr):
		i = s = t = 0
		arr.sort()
		if len(arr) > 1:
			while len(arr) > 2:
				s = arr[i] + arr[i + 1]
				arr.pop(0)
				arr.pop(0)
				bisect.insort(arr, s)
				t += s
		else:
			return 0
		return t + sum(arr)


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		net_sum = 0
		while len(arr) > 1:
			next_element = heapq.heappop(arr) + heapq.heappop(arr)
			net_sum += next_element
			heapq.heappush(arr, next_element)
		return net_sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		sum = 0
		while len(arr) > 1:
			no1 = heapq.heappop(arr)
			no2 = heapq.heappop(arr)
			sum = sum + no1 + no2
			heapq.heappush(arr, no1 + no2)
		return sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		heap = arr
		s = 0
		while len(heap) >= 2:
			x1 = heapq.heappop(heap)
			x2 = heapq.heappop(heap)
			s = s + x1 + x2
			heapq.heappush(heap, x1 + x2)
		return s


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		l = len(arr)
		op = 0
		while l > 1:
			x = heapq.heappop(arr)
			y = heapq.heappop(arr)
			heapq.heappush(arr, x + y)
			op = x + y + op
			l -= 1
		return op


import heapq

class Solution:

	def minimizeSum(self, n, arr):
		heapq.heapify(arr)
		summ = 0
		for i in range(n - 1):
			choice_sum = heapq.heappop(arr) + heapq.heappop(arr)
			summ += choice_sum
			heapq.heappush(arr, choice_sum)
		return summ


class Solution:

	def minimizeSum(self, N, arr):
		if N == 1:
			return 0
		import bisect
		sum = 0
		i = sorted(arr)
		while len(i) > 2:
			t = i[0] + i[1]
			sum += t
			i[1] = t
			i.pop(0)
			val = i.pop(0)
			new_idx = bisect.bisect(i, val)
			i.insert(new_idx, val)
		sum = sum + i[0] + i[1]
		return sum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		heapq.heapify(arr)
		(n, res) = (len(arr), 0)
		if n < 2:
			return 0
		while n > 0:
			if n < 2:
				res += heapq.heappop(arr)
				break
			if n == 2:
				res += heapq.heappop(arr)
				res += heapq.heappop(arr)
				break
			a = heapq.heappop(arr)
			b = heapq.heappop(arr)
			heapq.heappush(arr, a + b)
			res += a + b
			n -= 1
		return res


from heapq import heapify, heappush, heappop

class Solution:

	def minimizeSum(self, N, arr):
		ans = 0
		heapify(arr)
		while N > 1:
			min1 = heappop(arr)
			min2 = heappop(arr)
			ans += min1 + min2
			heappush(arr, min1 + min2)
			N -= 1
		return ans


import heapq

class Solution:

	def minimizeSum(self, N, elements):
		heap = [(elem, elem) for elem in elements]
		heapq.heapify(heap)
		total_sum = 0
		while len(heap) > 1:
			(a, a_original) = heapq.heappop(heap)
			(b, b_original) = heapq.heappop(heap)
			total_sum += a_original + b_original
			heapq.heappush(heap, (a + b, a_original + b_original))
		return total_sum


class Solution:

	def minimizeSum(self, N, arr):
		import heapq
		heapq.heapify(arr)
		l = len(arr)
		suma = 0
		while l > 1:
			n1 = heapq.heappop(arr)
			n2 = heapq.heappop(arr)
			heapq.heappush(arr, n1 + n2)
			suma += n1 + n2
			l -= 1
		return suma


from heapq import heappush, heappop, heapify

class Solution:

	def minimizeSum(self, N, arr):
		heapify(arr)
		sum = 0
		while len(arr) != 1:
			run_min_sum = heappop(arr) + heappop(arr)
			heappush(arr, run_min_sum)
			sum += run_min_sum
		return sum


import bisect

class Solution:

	def minimizeSum(self, N, arr):
		minSum = 0
		arr.sort()
		for i in range(len(arr)):
			temp = 0
			if len(arr) >= 2:
				temp += arr.pop(0)
				temp += arr.pop(0)
				minSum += temp
				bisect.insort(arr, temp)
			else:
				return minSum


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		if N == 1:
			return 0
		if N == 2:
			return arr[0] + arr[1]
		heapq.heapify(arr)
		s1 = 0
		while len(arr) != 1:
			l1 = heapq.heappop(arr)
			l2 = heapq.heappop(arr)
			s1 = s1 + l1 + l2
			heapq.heappush(arr, l1 + l2)
		return s1


from bisect import insort

class Solution:

	def minimizeSum(self, N, arr):
		arr.sort()
		tot = 0
		while len(arr) > 1:
			temp = arr[0] + arr[1]
			tot += temp
			arr.pop(0)
			arr.pop(0)
			insort(arr, temp)
		return tot


import heapq

class Solution:

	def minimizeSum(self, N, arr):
		if len(arr) < 2:
			return 0
		else:
			heapq.heapify(arr)
			temp = 0
			while len(arr) > 1:
				x = heapq.heappop(arr)
				y = heapq.heappop(arr)
				temp1 = x + y
				temp += temp1
				heapq.heappush(arr, temp1)
			return temp