Minimum sum

Given an array arr[] such that each element is in the range [0 – 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. Return a string without leading zeroes.

Examples :

Input: arr[] = [6, 8, 4, 5, 2, 3]
Output: 604
Explanation: The minimum sum is formed by numbers 358 and 246.

Input: arr[] = [5, 3, 0, 7, 4]
Output: 82
Explanation: The minimum sum is formed by numbers 35 and 047.

Input: arr[] = [9, 4]
Output: 13
Explanation: The minimum sum is formed by numbers 9 and 4.

Constraints:
1 ≤ arr.size() ≤ 10⁶
0 ≤ arr[i] ≤ 9

Approach 01:

class Solution {
public:
    string minSum(vector<int> &nums) {
        // Sort the array
        sort(nums.begin(), nums.end());

        int n = nums.size();
        int carryOver = 0;
        string resultSum;

        // Iterate through the array from the end to the beginning
        for (int i = n - 1; i >= 0; i -= 2) {
            // If we encounter a zero, stop
            if (nums[i] == 0)
                break;

            // If there are at least two elements, add them together
            if (i != 0) {
                int pairSum = carryOver + nums[i] + nums[i - 1];
                carryOver = pairSum / 10;
                resultSum += (pairSum % 10) + '0';
            } else {
                // Handle the last single element
                int singleSum = carryOver + nums[i];
                carryOver = singleSum / 10;
                resultSum += (singleSum % 10) + '0';
            }
        }

        // Add any remaining carry
        if (carryOver)
            resultSum += carryOver + '0';

        // Reverse the string to get the correct order
        reverse(resultSum.begin(), resultSum.end());

        return resultSum;
    }
};

class Solution:
    def minSum(self, nums):
        # Sort the list
        nums.sort()

        n = len(nums)
        carryOver = 0
        resultSum = ""

        # Iterate through the list from the end to the beginning
        i = n - 1
        while i >= 0:
            # If we encounter a zero, stop
            if nums[i] == 0:
                break

            # If there are at least two elements, add them together
            if i != 0:
                pairSum = carryOver + nums[i] + nums[i - 1]
                carryOver = pairSum // 10
                resultSum += str(pairSum % 10)
            else:
                # Handle the last single element
                singleSum = carryOver + nums[i]
                carryOver = singleSum // 10
                resultSum += str(singleSum % 10)
            
            i -= 2

        # Add any remaining carry
        if carryOver:
            resultSum += str(carryOver)

        # Reverse the string to get the correct order
        return resultSum[::-1]

Time Complexity

• Sorting the Array:

  The function first sorts the input vector nums, which takes \( O(N \log N) \), where \( N \) is the size of the array.

• Iterating through the Array:

  After sorting, the function iterates through the array in reverse order with a step of 2. This traversal takes \( O(N) \) time.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, resulting in \( O(N \log N) \).

Space Complexity

• Result String:

  The function constructs a string resultSum to store the sum of paired digits, which requires \( O(N) \) space in the worst case (if the number of digits in the sum is proportional to the size of the input).

• Auxiliary Variables:

  The function uses a few variables like carryOver and pairSum, which take up constant space \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(N) \) due to the storage required for the result string.