Minimum Sum Of Two Numbers Formed From Digits Of An Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in company
Chegg Inc.

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6 
4 0 3 7 6 5
5
6 1 2 4 3
Sample Output 1 :
403
160
Explanation for Sample Input 1 :
For the first test case, the minimum sum is formed by numbers 357 and 046, and their sum is 403.
For the second test case, the minimum sum is formed by numbers 24 and 136, and their sum is 160.
Sample Input 2 :
2
7
9 2 3 5 0 7 2
3
9 2 2
Sample Output 2 :
496
31
Hint

Can you solve it greedily?

Approaches (1)
Greedy 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.
Time Complexity

O(NlogN), where N is the size of the given array.

 

Here, we are first sorting the elements in the array, which takes O(NlogN) time, and then we are iterating through the array to calculate the firstNum and secondNum, and then we are adding the two string numbers that will take O(N) time. Hence, the overall time complexity is O(NlogN).

Space Complexity

O(N), where N is the size of the given array.

 

We are using the string ‘firstNum’, ‘secondNum’, both of which will have length ‘N’/2. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Sum Of Two Numbers Formed From Digits Of An Array
Full screen
Console