Given an array of digits (values are from 0 to 9), find the minimum possible sum of two numbers formed from digits of the array. All digits of the given array must be used to form the two numbers.
Any combination of digits may be used to form the two numbers to be summed.  Leading zeroes are permitted.
If forming two numbers is impossible (i.e. when n==0) then the "sum" is the value of the only number that can be formed.
 
 
Example 1:
Input:
N = 6
arr[] = {6, 8, 4, 5, 2, 3}
Output:
604
Explanation:
The minimum sum is formed by numbers 
358 and 246
 
Example 2:
Input:
N = 5
arr[] = {5, 3, 0, 7, 4}
Output:
82
Explanation:
The minimum sum is formed by numbers 
35 and 047
Your Task:
You don't have to print anything, printing is done by the driver code itself. Your task is to complete the function minSum() which takes the array A[] and its size N as inputs and returns the required sum.
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 35
0 ≤ A[] ≤ 9

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: class Solution:

    def minSum(self, arr, n):

        # Your code goes here

    

Solutions:
import heapq as h

class Solution:

	def minSum(self, arr, n):
		num1 = '0'
		num2 = '0'
		heap = []
		for i in range(0, n):
			h.heappush(heap, arr[i])
		while heap:
			if heap:
				num1 = num1 + str(h.heappop(heap))
			if heap:
				num2 = num2 + str(h.heappop(heap))
		return int(num1) + int(num2)


class Solution:

	def minSum(self, arr, n):
		if len(arr) == 1:
			return sum(arr)
		arr.sort()
		one = ''
		two = ''
		for i in range(len(arr)):
			if i % 2 == 0:
				one += str(arr[i])
			else:
				two += str(arr[i])
		return int(one) + int(two)


import sys
import heapq

class Solution:

	def minSum(self, arr, n):
		minheap = []
		first = 0
		second = 0
		for i in range(0, n):
			heapq.heappush(minheap, arr[i])
		flag = 0
		while len(minheap) > 0:
			if flag == 0:
				ele = heapq.heappop(minheap)
				first = first * 10 + ele
				flag = 1
			else:
				ele1 = heapq.heappop(minheap)
				second = second * 10 + ele1
				flag = 0
		su = first + second
		return su


import heapq

class Solution:

	def minSum(self, arr, n):
		first_number = 0
		second_number = 0
		heapq.heapify(arr)
		while len(arr) > 1:
			first = heapq.heappop(arr)
			second = heapq.heappop(arr)
			first_number = first_number * 10 + first
			second_number = second_number * 10 + second
		if len(arr) != 0:
			first = heapq.heappop(arr)
			if first_number > second_number:
				second_number = second_number * 10 + first
			else:
				first_number = first_number * 10 + first
		return first_number + second_number


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		num1 = 0
		num2 = 0
		i = 0
		while i < n:
			if i % 2 == 0:
				num1 = num1 * 10 + arr[i]
			else:
				num2 = num2 * 10 + arr[i]
			i += 1
		summ = num1 + num2
		return summ


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		num1 = 0
		num2 = 0
		for i in range(n):
			if i % 2 == 0:
				num1 = num1 * 10 + arr[i]
			else:
				num2 = num2 * 10 + arr[i]
		summ = num1 + num2
		return summ


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		if n == 1:
			return arr[0]
		s1 = ''
		s2 = ''
		for i in range(n):
			if i % 2 == 0:
				s1 += str(arr[i])
			else:
				s2 += str(arr[i])
		return int(s1) + int(s2)


class Solution:

	def minSum(self, arr, n):
		arr = sorted(arr)
		n1 = n2 = 0
		for i in range(n):
			if i % 2 == 0:
				n1 = n1 * 10 + arr[i]
			else:
				n2 = n2 * 10 + arr[i]
		return n1 + n2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		(s, s1) = (0, 0)
		for i in range(0, n, 2):
			s = s * 10 + arr[i]
		for i in range(1, n, 2):
			s1 = s1 * 10 + arr[i]
		k = s + s1
		return k


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		first = arr[1::2]
		second = arr[::2]
		first = ''.join((str(x) for x in first)) if first else '0'
		second = ''.join((str(x) for x in second)) if second else '0'
		return int(first) + int(second)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		num1 = '0'
		num2 = '0'
		for (i, num) in enumerate(arr):
			if i % 2 == 0:
				num1 += str(num)
			else:
				num2 += str(num)
		return int(num1) + int(num2)


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		(res1, res2) = ('', '')
		j = 1
		for i in range(0, n, 2):
			res1 += str(arr[i])
			if j < n:
				res2 += str(arr[j])
			j += 2
		return int(res1) + int(res2)


class Solution:

	def minSum(self, arr, n):
		a = sorted(arr, reverse=True)
		(s1, s2) = ('0', '0')
		while len(a):
			s1 += str(a.pop())
			if len(a) != 0:
				s2 += str(a.pop())
		return int(s1) + int(s2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		numm1 = 0
		numm2 = 0
		for i in range(n):
			if i % 2 == 0:
				numm1 = numm1 * 10 + arr[i]
			else:
				numm2 = numm2 * 10 + arr[i]
		return numm2 + numm1


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		sum = 0
		if n % 2 != 0:
			arr.insert(0, 0)
		m = n / 2
		arr.sort(reverse=True)
		i = 0
		j = 0
		while i < n and j < m:
			sum = sum + (arr[i] + arr[i + 1]) * 10 ** j
			i = i + 2
			j = j + 1
		return int(sum)


class Solution:

	def minSum(self, arr, n):
		arr = sorted(arr)
		(num1, num2) = (0, 0)
		for i in range(len(arr)):
			if i % 2:
				num2 = num2 * 10 + arr[i]
			else:
				num1 = num1 * 10 + arr[i]
		return num1 + num2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		if len(arr) == 1:
			return arr[0]
		l1 = ''
		l2 = ''
		for i in range(len(arr)):
			if i % 2 == 0:
				l1 += str(arr[i])
			else:
				l2 += str(arr[i])
		return int(l1) + int(l2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		a = 0
		b = 0
		for i in range(0, n):
			if i % 2 == 0:
				a = a * 10 + arr[i]
			else:
				b = b * 10 + arr[i]
		tot = a + b
		return tot


class Solution:

	def minSum(self, arr, n):
		arr = sorted(arr)
		a = 0
		b = 0
		for i in range(0, len(arr), 2):
			a = a * 10 + arr[i]
		for j in range(1, len(arr), 2):
			b = b * 10 + arr[j]
		return a + b


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		if n % 2 == 0:
			num1 = '0'
			num2 = '0'
			for i in range(0, n, 2):
				num1 += str(arr[i])
				num2 += str(arr[i + 1])
		else:
			num1 = str(arr[0])
			num2 = '0'
			for i in range(1, n, 2):
				num1 += str(arr[i])
				num2 += str(arr[i + 1])
		return int(num1) + int(num2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		min1 = 0
		min2 = 0
		for i in range(n):
			if i % 2 == 0:
				min1 = min1 * 10 + arr[i]
			else:
				min2 = min2 * 10 + arr[i]
		return min2 + min1


class Solution:

	def minSum(self, arr, n):
		first = '0'
		second = '0'
		while len(arr) != 0:
			first += str(min(arr))
			arr.remove(min(arr))
			if len(arr) != 0:
				second += str(min(arr))
				arr.remove(min(arr))
		return int(first) + int(second)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		s = ''
		s += str(arr[0])
		ss = ''
		b = False
		if n > 1:
			b = True
			ss += str(arr[1])
			b = True
		for i in range(2, n):
			if i % 2 == 0:
				s += str(arr[i])
			else:
				ss += str(arr[i])
		if b == True:
			return int(s) + int(ss)
		return int(s)


class Solution:

	def minSum(self, arr, n):
		ar = sorted(arr)
		(f, s) = ('0', '0')
		for i in range(n):
			if i % 2 == 1:
				f += str(ar[i])
			else:
				s += str(ar[i])
		return int(s) + int(f)


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		fir = ''
		sec = ''
		for i in arr:
			if len(fir) == len(sec):
				fir += str(i)
			else:
				sec += str(i)
		return int(fir) + int(sec)


class Solution:

	def minSum(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		arr.sort()
		first_list = []
		second_list = []
		for i in range(len(arr)):
			if i % 2 == 0:
				first_list.append(str(arr[i]))
			else:
				second_list.append(str(arr[i]))
		return int(''.join(first_list)) + int(''.join(second_list))


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		s1 = ''
		s2 = ''
		i = 0
		j = 1
		while i < len(arr):
			s1 += str(arr[i])
			i += 2
		while j < len(arr):
			s2 += str(arr[j])
			j += 2
		if len(s1) == 0:
			s1 = '0'
		if len(s2) == 0:
			s2 = '0'
		return int(s1) + int(s2)


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		s = []
		e = []
		arr.sort()
		for i in range(n):
			if i % 2 == 0:
				s.append(str(arr[i]))
			else:
				e.append(str(arr[i]))
		s = int(''.join(s))
		e = int(''.join(e))
		return s + e


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		q1 = []
		q2 = []
		for i in range(0, len(arr), 2):
			q1.append(arr[i])
		for i in range(1, len(arr), 2):
			q2.append(arr[i])
		sum = 0
		n1 = len(q1)
		n2 = len(q2)
		for i in q1:
			sum = sum + i * 10 ** (n1 - 1)
			n1 -= 1
		for i in q2:
			sum = sum + i * 10 ** (n2 - 1)
			n2 -= 1
		return sum


import math

class Solution:

	def minSum(self, arr, n):

		def convert_to_num(digits, num):
			ans = 0
			if len(num) == 0:
				return 0
			while digits:
				temp = num.pop(0)
				ans = ans + temp * 10 ** (digits - 1)
				digits -= 1
			return ans
		if n == 1:
			return arr[0]
		arr.sort()
		digits = int(math.ceil(n / 2))
		num1 = []
		num2 = []
		while arr and digits:
			num1.append(min(arr))
			arr.pop(0)
			if len(arr) == 0:
				break
			num2.append(min(arr))
			arr.pop(0)
			digits -= 1
		if num1[0] == 0:
			while num1 and num1[0] == 0:
				num1.pop(0)
		n1 = convert_to_num(len(num1), num1)
		n2 = convert_to_num(len(num2), num2)
		return n1 + n2


class Solution:

	def minSum(self, arr, n):
		a = sorted(arr)
		if len(a) == 1:
			return a[0]
		else:
			j = ''
			c = ''
			a = sorted(arr)
			for i in range(len(a)):
				if i % 2 != 0:
					j += str(a[i])
				else:
					c += str(a[i])
			return int(j) + int(c)


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		first = []
		second = []
		arr.sort()
		for i in range(n):
			if i % 2 == 0:
				first.append(arr[i])
			else:
				second.append(arr[i])
		number1 = ''
		number2 = ''
		for i in first:
			number1 += str(i)
		for i in second:
			number2 += str(i)
		n1 = int(number1)
		n2 = int(number2)
		return n1 + n2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		num = [0, 0]
		for i in range(n):
			p = i % 2
			num[p] = num[p] * 10 + arr[i]
		return sum(num)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		n1 = ''
		n2 = ''
		for i in range(0, len(arr), 2):
			n1 = n1 + str(arr[i])
		for i in range(1, len(arr), 2):
			n2 = n2 + str(arr[i])
		if n2 == '':
			return int(n1)
		sum = int(n1) + int(n2)
		return sum


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		l = []
		ll = []
		if len(arr) == 1:
			return arr[0]
		else:
			for i in range(len(arr)):
				if i % 2 == 1:
					ll.append(str(arr[i]))
				elif i % 2 == 0:
					l.append(str(arr[i]))
		l = int(''.join(l))
		ll = int(''.join(ll))
		return abs(l + ll)


class Solution:

	def minSum(self, arr, n):
		import heapq
		heapq.heapify(arr)
		s1 = ' '
		s2 = ' '
		if n == 1:
			return arr[0]
		for i in range(0, n):
			if i % 2 == 0:
				a = heapq.heappop(arr)
				s1 += str(a)
			else:
				b = heapq.heappop(arr)
				s2 += str(b)
		return int(s1) + int(s2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		a = 0
		b = 0
		for i in range(0, n, 2):
			try:
				a = a * 10 + arr[i]
				b = b * 10 + arr[i + 1]
			except:
				pass
		return a + b


import heapq

class Solution:

	def minSum(self, arr, n):
		if len(arr) < 2:
			return arr[0]
		heapq.heapify(arr)
		a = ''
		b = ''
		while len(arr) > 0:
			if len(a) > len(b):
				b += str(heapq.heappop(arr))
			else:
				a += str(heapq.heappop(arr))
		sum = int(a) + int(b)
		return sum


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		else:
			arr.sort()
			ans1 = []
			ans2 = []
			sum = 0
			for i in range(0, n):
				if i % 2 == 1:
					ans1.append(str(arr[i]))
				else:
					ans2.append(str(arr[i]))
			ans1 = int(''.join(ans1))
			ans2 = int(''.join(ans2))
		return ans1 + ans2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		num1 = 0
		num2 = 0
		for i in range(0, n, 2):
			num1 = num1 * 10 + arr[i]
		for i in range(1, n, 2):
			num2 = num2 * 10 + arr[i]
		return num1 + num2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		f = s = 0
		for i in range(n):
			if i % 2 == 0:
				f = f * 10 + arr[i]
			else:
				s = s * 10 + arr[i]
		return s + f


class Solution:

	def minSum(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		arr.sort()
		str1 = ''
		str2 = ''
		i = 0
		while i < len(arr):
			if i % 2 == 0:
				str1 += str(arr[i])
			else:
				str2 += str(arr[i])
			i += 1
		sum1 = int(str1) + int(str2)
		return sum1


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		t = 1
		sm = 0
		while bool(arr):
			sm += t * arr.pop()
			if arr:
				sm += t * arr.pop()
			t *= 10
		return sm


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		a = []
		b = []
		for i in range(n):
			if i % 2 == 0:
				a.append(str(arr[i]))
			else:
				b.append(str(arr[i]))
		a = int(''.join(a))
		b = int(''.join(b))
		return a + b


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		val1 = ''
		val2 = ''
		if len(arr) == 1:
			return arr[0]
		for i in range(n):
			if i % 2 == 0:
				val1 += str(arr[i])
			else:
				val2 += str(arr[i])
		return int(val1) + int(val2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		if len(arr) == 1:
			return arr[0]
		value1 = str()
		value2 = str()
		i = 0
		while i < len(arr):
			value1 += str(arr[i])
			i += 2
		i = 1
		while i < len(arr):
			value2 += str(arr[i])
			i += 2
		return int(value1) + int(value2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		e = '0'
		o = '0'
		for i in range(0, n):
			if i % 2 == 0:
				e += str(arr[i])
			else:
				o += str(arr[i])
		return int(e) + int(o)


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		num = ['', '']
		arr.sort()
		for x in range(n):
			num[x & 1] += str(arr[x])
		return sum(map(int, num))


class Solution:

	def minSum(self, arr, n):
		q1 = []
		q2 = []
		arr.sort()
		if n == 1:
			return arr[0]
		for i in range(0, n, 2):
			q1.append(arr[i])
		for i in range(1, n, 2):
			q2.append(arr[i])
		num1 = int(''.join(map(str, q1)))
		num2 = int(''.join(map(str, q2)))
		return num1 + num2


class Solution:

	def minSum(self, arr, n):
		es = '0'
		os = '0'
		arr = sorted(arr)
		for i in range(n):
			if i & 1 == 0:
				es += str(arr[i])
			else:
				os += str(arr[i])
		es = int(es)
		os = int(os)
		return es + os


class Solution:

	def minSum(self, arr, n):
		min_sum = ''
		min_sum1 = ''
		while arr != []:
			min_sum += str(min(arr))
			arr.remove(min(arr))
			if arr != []:
				min_sum1 += str(min(arr))
				arr.remove(min(arr))
		if len(min_sum) != 0 and len(min_sum1) != 0:
			return int(min_sum) + int(min_sum1)
		elif len(min_sum) != 0 and len(min_sum1) == 0:
			return int(min_sum)
		else:
			return 0


class Solution:

	def minSum(self, arr, n):
		if n == 1:
			return arr[0]
		n1 = ''
		n2 = ''
		arr.sort()
		for i in range(n):
			if i % 2 == 0:
				n1 += str(arr[i])
			else:
				n2 += str(arr[i])
		s = int(n1) + int(n2)
		return s


import heapq

class Solution:

	def minSum(self, arr, n):
		n1 = 0
		n2 = 0
		heapq.heapify(arr)
		while 1:
			if len(arr) > 0:
				n1 = n1 * 10 + heapq.heappop(arr)
			if len(arr) > 0:
				n2 = n2 * 10 + heapq.heappop(arr)
			else:
				break
		ans = int(n1) + int(n2)
		return ans


import heapq

class Solution:

	def minSum(self, arr, n):
		if len(arr) == 1:
			return sum(arr)
		h = []
		for i in range(n):
			heapq.heappush(h, arr[i])
		c = ''
		d = ''
		while len(h) != 0:
			s1 = heapq.heappop(h)
			c += str(s1)
			if len(h) != 0:
				s2 = heapq.heappop(h)
				d += str(s2)
		n1 = int(c)
		n2 = int(d)
		return n1 + n2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		arr1 = []
		arr2 = []
		if len(arr) == 1:
			return arr[0]
		while len(arr) > 0:
			ele = arr.pop(0)
			arr1.append(str(ele))
			if len(arr) != 0:
				new = arr.pop(0)
				arr2.append(str(new))
		x = ''.join(arr1)
		y = ''.join(arr2)
		sum = int(x) + int(y)
		return sum


class Solution:

	def minSum(self, arr, n):
		arr = sorted(arr)
		a = 0
		b = 0
		for i in range(len(arr)):
			if i % 2 == 0:
				a = a * 10 + arr[i]
			else:
				b = b * 10 + arr[i]
		return a + b


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		a = ''
		b = ''
		i = 0
		if len(arr) == 1:
			return arr[0]

		def sort(arr, i, a, b):
			if i % 2 == 0:
				a += str(arr[i])
			else:
				b += str(arr[i])
			if i == len(arr) - 1:
				return int(a) + int(b)
			return sort(arr, i + 1, a, b)
		return sort(arr, i, a, b)


from heapq import *

class Solution:

	def minSum(self, arr, n):
		minheap = []
		for i in range(n):
			heappush(minheap, arr[i])
		num1 = 0
		num2 = 0
		while minheap:
			num1 = num1 * 10 + heappop(minheap)
			if minheap:
				num2 = num2 * 10 + heappop(minheap)
		return num1 + num2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		if n <= 2:
			return sum(arr)
		(temp1, temp2) = (arr[::2], arr[1::2])

		def convert(a):
			num = str()
			for i in a:
				num += str(i)
			num = int(num)
			return num
		(num1, num2) = (convert(temp1), convert(temp2))
		ans = num1 + num2
		return ans


class Solution:

	def minSum(self, arr, n):
		if n > 1:
			arr.sort()
			i = 0
			num1 = str()
			num2 = str()
			if n % 2 == 0:
				while i < n:
					num1 += str(arr[i])
					num2 += str(arr[i + 1])
					i += 2
			else:
				while i < n - 1:
					num1 += str(arr[i])
					num2 += str(arr[i + 1])
					i += 2
				num1 += str(arr[n - 1])
			return int(num1) + int(num2)
		else:
			return arr[0]


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		(sum1, sum2) = (0, 0)
		for i in range(n):
			if i % 2 == 0:
				sum1 = sum1 * 10 + arr[i]
			else:
				sum2 = sum2 * 10 + arr[i]
		return sum1 + sum2


from heapq import *

class Solution:

	def minSum(self, arr, n):
		heap = []
		a1 = ''
		a2 = ''
		if len(arr) <= 1:
			return arr[0]
		for i in arr:
			heappush(heap, i)
		while len(heap) > 1:
			a = heappop(heap)
			b = heappop(heap)
			a1 += str(a)
			a2 += str(b)
		if len(heap) != 0:
			a1 += str(heappop(heap))
		return int(a2) + int(a1)


class Solution:

	def minSum(self, arr, n):
		arr.sort(reverse=True)
		num1 = '0'
		num2 = '0'
		for i in range(n // 2):
			num1 += str(arr.pop())
			num2 += str(arr.pop())
		if arr:
			num1 += str(arr.pop())
		return int(num1) + int(num2)


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		n1 = 0
		n2 = 0
		for i in range(0, n, 2):
			n1 = n1 * 10 + arr[i]
		for i in range(1, n, 2):
			n2 = n2 * 10 + arr[i]
		return n1 + n2


class Solution:

	def minSum(self, arr, n):
		arr.sort()
		p1 = '0'
		p2 = '0'
		for n in range(0, len(arr), 2):
			p1 += str(arr[n])
			if n + 1 < len(arr):
				p2 += str(arr[n + 1])
		return int(p1) + int(p2)


import heapq

class Solution:

	def minSum(self, arr, n):
		heapq.heapify(arr)
		left = True
		st1 = []
		st2 = []
		i = 0
		while len(arr) > 0:
			if left:
				heapq.heappush(st1, str(heapq.heappop(arr)))
				left = False
			else:
				heapq.heappush(st2, str(heapq.heappop(arr)))
				left = True
		a = int(''.join(st1))
		b = 0
		if len(st2) > 0:
			b = int(''.join(st2))
		return a + b