Minimum sum of two numbers formed from digits of an array
Last Updated :
03 Jan, 2023
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 given array must be used to form the two numbers.
Examples:
Input: [6, 8, 4, 5, 2, 3]
Output: 604
The minimum sum is formed by numbers
358 and 246
Input: [5, 3, 0, 7, 4]
Output: 82
The minimum sum is formed by numbers
35 and 047
Since we want to minimize the sum of two numbers to be formed, we must divide all digits in two halves and assign half-half digits to them. We also need to make sure that the leading digits are smaller.
We build a Min Heap with the elements of the given array, which takes O(n) worst time. Now we retrieve min values (2 at a time) of array, by polling from the Priority Queue and append these two min values to our numbers, till the heap becomes empty, i.e., all the elements of array get exhausted. We return the sum of two formed numbers, which is our required answer. Overall complexity is O(nlogn) as push() operation takes O(logn) and it’s repeated n times.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
int minSum(int arr[], int n)
{
priority_queue <int, vector<int>, greater<int> > pq;
string num1, num2;
for(int i=0; i<n; i++)
pq.push(arr[i]);
while(!pq.empty())
{
num1+=(48 + pq.top());
pq.pop();
if(!pq.empty())
{
num2+=(48 + pq.top());
pq.pop();
}
}
int a = atoi(num1.c_str());
int b = atoi(num2.c_str());
return a+b;
}
int main()
{
int arr[] = {6, 8, 4, 5, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<minSum(arr, n)<<endl;
return 0;
}
|
Java
import java.util.PriorityQueue;
class MinSum
{
public static long solve(int[] a)
{
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
StringBuilder num1 = new StringBuilder();
StringBuilder num2 = new StringBuilder();
for (int x : a)
pq.add(x);
while (!pq.isEmpty())
{
num1.append(pq.poll()+ "");
if (!pq.isEmpty())
num2.append(pq.poll()+ "");
}
long sum = Long.parseLong(num1.toString()) +
Long.parseLong(num2.toString());
return sum;
}
public static void main (String[] args)
{
int arr[] = {6, 8, 4, 5, 2, 3};
System.out.println("The required sum is "+ solve(arr));
}
}
|
Python3
from queue import PriorityQueue
def solve(a):
pq = PriorityQueue()
num1 = ""
num2 = ""
for x in a:
pq.put(x)
while not pq.empty():
num1 += str(pq.get())
if not pq.empty():
num2 += str(pq.get())
sum = int(num1) + int(num2)
return sum
if __name__=="__main__":
arr = [ 6, 8, 4, 5, 2, 3 ]
print("The required sum is ", solve(arr))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public static long solve(int[] a)
{
List<int> pq = new List<int>();
string num1 = "";
string num2 = "";
foreach(int x in a)
pq.Add(x);
pq.Sort();
while (pq.Count > 0)
{
num1 = num1 + pq[0];
pq.RemoveAt(0);
if (pq.Count > 0)
{
num2 = num2 + pq[0];
pq.RemoveAt(0);
}
}
int sum = Int32.Parse(num1) + Int32.Parse(num2);
return sum;
}
static void Main()
{
int[] arr = {6, 8, 4, 5, 2, 3};
Console.WriteLine("The required sum is "+ solve(arr));
}
}
|
Javascript
<script>
function solve(a)
{
pq=[];
let num1="";
let num2="";
for(let x=0;x<a.length;x++)
{
pq.push(a[x]);
}
pq.sort(function(a,b){return b-a;});
while(pq.length!=0)
{
num1+=pq.pop();
if(pq.length!=0)
{
num2+=pq.pop();
}
}
let sum=parseInt(num1)+parseInt(num2);
return sum;
}
let arr=[6, 8, 4, 5, 2, 3];
document.write("The required sum is "+ solve(arr));
</script>
|
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Another method: We can follow another approach also like this, as we need two numbers such that their sum is minimum, then we would also need two minimum numbers. If we arrange our array in ascending order then we can two digits that will form the smallest numbers,
e.g., 2 3 4 5 6 8, now we can get two numbers starting from 2 and 3. First part is done now. Moving forward we have to form such that they would contain small digits, i.e. pick digits alternatively from array extend your two numbers.
i.e. 246, 358. Now if we see analyze this, then we can pick even indexed numbers for num1 and an odd number for num2.
Below is the implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int minSum(int a[], int n)
{
sort(a, a + n);
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * 10 + a[i];
else
num2 = num2 * 10 + a[i];
}
return num2 + num1;
}
int main()
{
int arr[] = { 5, 3, 0, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The required sum is " << minSum(arr, n)
<< endl;
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int minSum(int a[], int n)
{
qsort(a, n, sizeof(int), cmpfunc);
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * 10 + a[i];
else
num2 = num2 * 10 + a[i];
}
return num2 + num1;
}
int main()
{
int arr[] = { 5, 3, 0, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The required sum is %d", minSum(arr, n));
return 0;
}
|
Java
import java.util.Arrays;
public class AQRQ {
static int minSum(int a[], int n)
{
Arrays.sort(a);
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * 10 + a[i];
else
num2 = num2 * 10 + a[i];
}
return num2 + num1;
}
public static void main(String[] args)
{
int arr[] = { 5, 3, 0, 7, 4 };
int n = arr.length;
System.out.println("The required sum is "
+ minSum(arr, n));
}
}
|
Python3
def minSum(a, n):
a = sorted(a)
num1, num2 = 0, 0
for i in range(n):
if i % 2 == 0:
num1 = num1 * 10 + a[i]
else:
num2 = num2 * 10 + a[i]
return num2 + num1
arr = [5, 3, 0, 7, 4]
n = len(arr)
print("The required sum is",
minSum(arr, n))
|
C#
using System;
public class GFG{
static int minSum(int []a, int n){
Array.Sort(a);
int num1 = 0;
int num2 = 0;
for(int i = 0;i<n;i++){
if(i%2==0)
num1 = num1*10+a[i];
else num2 = num2*10+a[i];
}
return num2+num1;
}
static public void Main (){
int []arr = {5, 3, 0, 7, 4};
int n = arr.Length;
Console.WriteLine("The required sum is " + minSum(arr, n));
}
}
|
PHP
<?php
function minSum($a, $n)
{
sort($a);
$num1 = 0;
$num2 = 0;
for($i = 0; $i < $n; $i++)
{
if($i % 2 == 0)
$num1 = $num1 * 10 + $a[$i];
else $num2 = $num2 * 10 + $a[$i];
}
return ($num2 + $num1);
}
$arr = array(5, 3, 0, 7, 4);
$n = sizeof($arr);
echo "The required sum is ",
minSum($arr, $n), "\n";
?>
|
Javascript
<script>
function minSum(a, n){
a.sort();
let num1 = 0;
let num2 = 0;
for(let i = 0;i<n;i++){
if(i%2==0)
num1 = num1*10+a[i];
else num2 = num2*10+a[i];
}
return num2+num1;
}
let arr = [5, 3, 0, 7, 4];
let n = arr.length;
document.write("The required sum is " + minSum(arr, n));
</script>
|
Output
The required sum is 82
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Please Login to comment...