Given an array Arr of size N such that each element is from the range 0 to 9. Find the minimum possible sum of two numbers formed using the elements of the array. All digits in the given array must be used to form the two numbers.
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 need to read input or print anything. Your task is to complete the function solve() which takes arr[] and n as input parameters and returns the minimum possible sum. As the number can be large, return string presentation of the number without leading zeroes.
 
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ Arr_{i} ≤ 9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def solve(self, arr, n):

        # code here

Solutions:
import heapq

class Solution:

	def solve(self, arr, n):
		min_heap = []
		for num in arr:
			heapq.heappush(min_heap, num)
		num1 = 0
		num2 = 0
		while len(min_heap) > 1:
			a = heapq.heappop(min_heap)
			b = heapq.heappop(min_heap)
			num1 = num1 * 10 + a
			num2 = num2 * 10 + b
		if len(min_heap):
			a = heapq.heappop(min_heap)
			if num1 < num2:
				num1 = num1 * 10 + a
			else:
				num2 = num2 * 10 + a
		return num1 + num2


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def solve(self, arr, n):
		if n <= 2:
			return sum(arr)
		arr.sort()
		ist = ''
		nd = ''
		i = 1
		while i <= n:
			ist += str(arr[i - 1])
			if i == n:
				break
			else:
				nd += str(arr[i])
			i += 2
		return int(ist) + int(nd)


class Solution:

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


class Solution:

	def solve(self, arr, n):
		arr = sorted(arr)
		e = 0
		o = 0
		for i in range(n):
			if i % 2 == 0:
				e = e * 10 + arr[i]
			else:
				o = o * 10 + arr[i]
		return str(e + o)


class Solution:

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


class Solution:

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


class Solution:

	def solve(self, arr, n):
		s1 = ''
		s2 = ''
		arr.sort()
		if len(arr) == 1:
			return arr[0]
		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 solve(self, arr, n):
		arr.sort()
		f = ''
		s = ''
		for i in range(n):
			if i % 2 == 0:
				f += str(arr[i])
			else:
				s += str(arr[i])
		if f == '':
			f = '0'
		if s == '':
			s = '0'
		return int(f) + int(s)


import heapq

class Solution:

	def solve(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		s1 = ''
		s2 = ''
		heap = []
		for i in range(n):
			heapq.heappush(heap, arr[i])
		while len(heap) > 0:
			s1 += str(heapq.heappop(heap))
			if len(heap) == 0:
				break
			s2 += str(heapq.heappop(heap))
		return int(s1) + int(s2)


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def solve(self, arr, n):
		if len(arr) < 2:
			return arr[0]
		arr.sort()
		flag = 1
		str1 = ''
		str2 = ''
		for i in range(n):
			if flag == 1:
				str1 += str(arr[i])
				flag = 0
			elif flag == 0:
				str2 += str(arr[i])
				flag = 1
		return int(str1) + int(str2)


class Solution:

	def solve(self, arr, n):
		if len(arr) == 1:
			return arr[0]
		arr.sort()
		l = arr[::2]
		arr = arr[1::2]
		l = list(map(str, l))
		arr = list(map(str, arr))
		l = ''.join(l)
		arr = ''.join(arr)
		l = int(l)
		arr = int(arr)
		return l + arr


class Solution:

	def solve(self, arr, n):
		arr.sort()
		if n == 1:
			return arr[0]
		num1 = ''.join(map(str, arr[::2]))
		num2 = ''.join(map(str, arr[1::2]))
		return int(num1) + int(num2)


class Solution:

	def solve(self, arr, n):
		arr.sort()
		a = ''
		b = ''
		for i in range(0, n, 2):
			a = a + str(arr[i])
		for j in range(1, n, +2):
			b = b + str(arr[j])
		if a == '' and b != '':
			return int(b)
		elif a != '' and b == '':
			return int(a)
		else:
			return int(a) + int(b)


class Solution:

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


class Solution:

	def solve(self, arr, n):
		e = 0
		o = 0
		arr.sort()
		for j in range(1, n, 2):
			o = str(o) + str(arr[j])
		for i in range(0, n, 2):
			e = str(e) + str(arr[i])
		return int(o) + int(e)


from queue import PriorityQueue

def min_sum_two_number(input_arr: [], n: int):
	if len(input_arr) == 0:
		return 0
	if len(input_arr) == 1:
		return input_arr[0]
	input_arr = sorted(input_arr)
	string_1 = ''
	string_2 = ''
	i = 0
	while i < n:
		string_1 = string_1 + str(input_arr[i])
		i = i + 1
		if i < n:
			string_2 = string_2 + str(input_arr[i])
			i = i + 1
	value_1 = int(string_1)
	value_2 = int(string_2)
	return value_2 + value_1

class Solution:

	def solve(self, arr, n):
		return min_sum_two_number(arr, n)


class Solution:

	def solve(self, arr, n):
		arr.sort()
		(first, second) = (arr[::2], arr[1::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 solve(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		esum = ''
		osum = ''
		for i in range(n):
			if i % 2 == 0:
				esum += str(arr[i])
			else:
				osum += str(arr[i])
		return int(esum) + int(osum)


class Solution:

	def solve(self, arr, n):
		l = ''
		m = ''
		k = sorted(arr)
		for i in range(0, n, 2):
			l += str(k[i])
		for i in range(1, n, 2):
			m += str(k[i])
		if len(l) == 0:
			l = '0'
		if len(m) == 0:
			m = '0'
		return int(l) + int(m)


class Solution:

	def solve(self, arr, n):
		arr.sort()
		s1 = ''
		s2 = ''
		flag = 0
		for i in arr:
			if flag == 0:
				s1 += str(i)
				flag = 1
			else:
				s2 += str(i)
				flag = 0
		if s1 == '':
			s1 = '0'
		if s2 == '':
			s2 = '0'
		return int(s1) + int(s2)


class Solution:

	def solve(self, arr, n):
		arr.sort()
		n1 = 0
		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 solve(self, arr, n):
		arr.sort()
		a = 0
		b = 0
		i = 0
		while i < len(arr):
			a = a * 10 + arr[i]
			i += 1
			if i == len(arr):
				break
			b = b * 10 + arr[i]
			i += 1
		return str(a + b)


class Solution:

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


class Solution:

	def solve(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		lst1 = ''
		lst2 = ''
		for i in range(0, n, 2):
			q = str(arr[i])
			lst1 = lst1 + q
		for i in range(1, n, 2):
			w = str(arr[i])
			lst2 = lst2 + w
		k = int(lst1)
		m = int(lst2)
		return k + m


class Solution:

	def solve(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		lst1 = ''
		lst2 = ''
		for i in range(0, n, 2):
			q = str(arr[i])
			lst1 = lst1 + q
		for i in range(1, n, 2):
			t = str(arr[i])
			lst2 = lst2 + t
		e = int(lst1)
		r = int(lst2)
		return e + r


class Solution:

	def solve(self, arr, n):
		if n == 1:
			return arr[0]
		arr.sort()
		s = ''
		p = ''
		for i in range(0, len(arr), 2):
			s += str(arr[i])
		for j in range(1, len(arr), 2):
			p += str(arr[j])
		return int(s) + int(p)


class Solution:

	def solve(self, arr, n):
		arr.sort()
		x = ''
		y = ''
		for i in range(0, n, 2):
			x += str(arr[i])
			if i + 1 < n:
				y += str(arr[i + 1])
		if x != '':
			x = int(x)
		else:
			x = 0
		if y != '':
			y = int(y)
		else:
			y = 0
		return x + y


class Solution:

	def solve(self, arr, n):
		num1 = 0
		num2 = 0
		arr.sort()
		arr.reverse()
		while len(arr) > 1:
			num1 *= 10
			num2 *= 10
			num1 += arr[-1]
			num2 += arr[-2]
			arr.pop()
			arr.pop()
		if arr:
			(num1, num2) = (min(num1, num2) * 10 + arr[-1], max(num1, num2))
		return num1 + num2


class Solution:

	def solve(self, arr, n):
		if n == 1:
			return str(arr[0])
		arr.sort()
		r = ''
		l = ''
		for i in range(0, n, 2):
			l = l + str(arr[i])
		for i in range(1, n, 2):
			r = r + str(arr[i])
		k = int(l) + int(r)
		return str(k)


import heapq

class Solution:

	def solve(self, arr, n):
		heapq.heapify(arr)
		a = 0
		b = 0
		i = 0
		while i < n:
			if i % 2 == 0:
				a = a * 10 + heapq.heappop(arr)
			else:
				b = b * 10 + heapq.heappop(arr)
			i += 1
		return a + b


class Solution:

	def solve(self, arr, n):
		arr.sort()
		first = 0
		last = 0
		for i in range(0, len(arr), 2):
			first = first * 10 + arr[i]
		for i in range(1, len(arr), 2):
			last = last * 10 + arr[i]
		return first + last


import heapq

class Solution:

	def solve(self, array, n):
		heap = []
		for item in array:
			heapq.heappush(heap, item)
		number1 = 0
		number2 = 0
		while heap:
			item1 = heapq.heappop(heap)
			number1 = number1 * 10 + item1
			if len(heap) > 0:
				item2 = heapq.heappop(heap)
				number2 = number2 * 10 + item2
		return number1 + number2


class Solution:

	def solve(self, arr, n):
		arr.sort()
		ans1 = 0
		ans2 = 0
		i = 0
		while i < n:
			ans1 = ans1 * 10 + arr[i]
			i += 2
		i = 1
		while i < n:
			ans2 = ans2 * 10 + arr[i]
			i += 2
		ans = ans1 + ans2
		return str(ans)


class Solution:

	def solve(self, arr, n):
		arr.sort()
		(a, b) = (0, 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 solve(self, arr, n):
		if n == 1:
			return arr[n - 1]
		arr.sort()
		firstnum = ''
		secondnum = ''
		for i in range(len(arr)):
			if i % 2 != 0:
				firstnum += str(arr[i])
			elif i % 2 == 0:
				secondnum += str(arr[i])
		return int(firstnum) + int(secondnum)


class Solution:

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


class Solution:

	def solve(self, arr, n):
		arr.sort()
		if n == 1:
			return arr[0]
		if n == 2:
			return arr[0] + arr[1]
		s = 0
		num1 = arr[0]
		while s < n:
			if s != 0:
				num1 = num1 * 10 + arr[s]
			s += 2
		num2 = arr[1]
		s = 1
		while s < n:
			if s != 1:
				num2 = num2 * 10 + arr[s]
			s += 2
		return num1 + num2


class Solution:

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