{x}
blog image

Minimum Sum of Four Digit Number After Splitting Digits

You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num. Leading zeros are allowed in new1 and new2, and all the digits found in num must be used.

  • For example, given num = 2932, you have the following digits: two 2's, one 9 and one 3. Some of the possible pairs [new1, new2] are [22, 93], [23, 92], [223, 9] and [2, 329].

Return the minimum possible sum of new1 and new2.

 

Example 1:

Input: num = 2932
Output: 52
Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc.
The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52.

Example 2:

Input: num = 4009
Output: 13
Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc. 
The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.

 

Constraints:

  • 1000 <= num <= 9999

Solution Explanation

The problem asks to find the minimum sum of two four-digit numbers created by splitting the digits of a given four-digit number. The key insight is that to minimize the sum, we should pair the smallest two digits together and the largest two digits together. This is because placing smaller digits in the tens place of one number and the ones place of the other will result in a smaller sum than the reverse.

Approach

  1. Extract Digits: Extract the four digits from the input number num.
  2. Sort Digits: Sort the digits in ascending order.
  3. Form Numbers: Create new1 using the smallest two digits (placing the smaller digit in the tens place) and new2 using the largest two digits (placing the larger digit in the tens place).
  4. Calculate Sum: Return the sum of new1 and new2.

Time and Space Complexity

  • Time Complexity: O(1) or O(log n) depending on the sorting algorithm used. Since we're dealing with a fixed number of digits (four), the sorting takes constant time. If a general sorting algorithm were used that scales with n, it would be O(log n) due to the use of efficient sorting algorithms with that time complexity.
  • Space Complexity: O(1). We use a constant amount of extra space to store the digits.

Code Explanation (Python)

class Solution:
    def minimumSum(self, num: int) -> int:
        nums = []
        while num:
            nums.append(num % 10)
            num //= 10
        nums.sort()
        return 10 * (nums[0] + nums[1]) + nums[2] + nums[3]
  1. nums = []: An empty list is created to store the digits.
  2. while num:: This loop iterates until num becomes 0.
  3. nums.append(num % 10): The last digit of num (obtained using the modulo operator %) is appended to the nums list.
  4. num //= 10: Integer division (//) removes the last digit from num.
  5. nums.sort(): The nums list is sorted in ascending order.
  6. return 10 * (nums[0] + nums[1]) + nums[2] + nums[3]: This line constructs new1 and new2 implicitly and calculates their sum. It cleverly forms the numbers and adds them together in one efficient expression. 10 * (nums[0] + nums[1]) creates a number with the two smallest digits, and nums[2] + nums[3] creates the second number with the two largest digits, then they are added.

The other language implementations follow a similar approach, differing only in syntax and data structure usage. The core logic remains consistent across all languages.