Minimum sum of two numbers formed from digits of an array
Problem
Use every digit in the array exactly once to form two numbers whose sum is as small as possible. Return that sum.
Example 1
Input: [6, 8, 4, 5, 2, 3] Output: 604
246 + 358.
Also asked as: Minimum sum of two numbers formed from digits of an array
Test cases
Case 1
Input: [6,8,4,5,2,3] Expected: "604"
Case 2
Input: [5,3,0,7,4] Expected: "82"
Case 3
Input: [2,3] Expected: "5"
Case 4
Input: [1] Expected: "1"
View solutionHide solution1 approach
1. Sort ascending, deal digits alternately to two numbers
Time O(n log n)Space O(n)
Smallest digits belong in the highest place values; alternating them between the two numbers keeps both small and equal in length.
function minSum(digits) { digits.sort((a, b) => a - b); let n1 = '', n2 = ''; digits.forEach((d, i) => (i % 2 === 0 ? (n1 += d) : (n2 += d))); return (BigInt(n1 || 0) + BigInt(n2 || 0)).toString();}