Last Updated: 19 Feb, 2021

Minimum Sum Of Two Numbers Formed From Digits Of An Array

Easy

Asked in company

Solve now

Problem statement

Given an array of integers “ARR” in which value of each element is between 0 and 9(both inclusive), You are supposed to construct two numbers by concatenating the elements of ARR and find the minimum possible sum of two numbers formed using the elements of the array.

Note: Each element of the given array must be a part of exactly one number.

Input Format :

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains N space-separated integers denoting the elements of the array ARR.

Output Format :

For each test case, on a separate line, output one integer - the minimum possible sum of numbers.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10^4
0 <= A[i] <= 9

Where ‘T’ is the number of test cases, ‘N’  is the size of the given array, and ‘ARR[i]’ denotes the ith element of the array.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to sort the array in ascending order and then concatenate the array elements alternatively to the first and the second number. So, the first number is formed by the elements present in the even position and the second number is formed by the elements present in the odd position. The sum of the first and the second number will be the minimum sum.

The algorithm is as follows :

Sort the array in ascending order.
Maintain two string variables firstNum and secondNum, we are using a string to store the numbers since N is large and it will not be possible to store the number in any variable of the primitive data type.
Iterate from i = 0 to N-1
1. If i is even, then append ARR[i] to firstNum.
2. If i is odd, then append ARR[i] to secondNum.
Finally, add the two strings numbers firstNum and secondNum to get the minimum sum.
1. Maintain two pointers firstPtr and secondPtr, for firstNum and secondNum, start traversing both the strings backwards.
2. Declare a carry variable to store the carry while adding two digits.
3. Declare an empty string ans to store the sum of the firstNum and secondNum.
4. Repeat the following steps till firstPtr >= 0 or secondPtr >= 0 or carry != 0.
  1. Declare a variable sum to 0 to store the digits of ans.
  2. If firstPtr >= 0, add firstNum[ptr1] to sum and decrement firstPtr by 1.
  3. If secondPtr >= 0, add secondNum[ptr2] to sum and decrement secondPtr by 1.
  4. Add carry to sum.
  5. Extract the last digit of sum and append it to ans.
Update carry to sum / 10.
Finally, reverse the string ans.
Remove the leading zero’s from ans if any.
Return the ans.

Solve now