Scale Engineer

Minimum Sum of Four Digit Number After Splitting Digits

Easy
#1967Time: O(1). The number of digits is fixed at 4. The number of unique permutations of 4 items is at most `4! = 24`. For each permutation, we perform a constant number of splits and calculations. Therefore, the total number of operations is constant and does not depend on the value of `num`.Space: O(1). We need space to store the digits and the permutations. Since the number of digits is fixed at 4, the space required is also constant.
Patterns
MathGreedy
Algorithms
Sorting

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores all possible ways to arrange the four digits and all possible ways to split them into two numbers. It's a "brute-force" method because it doesn't use any specific insight about the problem structure, instead relying on exhaustive search to find the minimum sum.

Algorithm

  • Convert the 4-digit number num into a list of its individual digits.
  • Implement a function to generate all unique permutations of this list of digits.
  • Initialize a variable minSum to a very large value (e.g., Integer.MAX_VALUE).
  • Iterate through each unique permutation of the digits.
  • For each permutation (d1, d2, d3, d4):
    • a. Calculate the sum for a 1-digit/3-digit split: sum1 = d1 + (100*d2 + 10*d3 + d4). Update minSum = min(minSum, sum1).
    • b. Calculate the sum for a 2-digit/2-digit split: sum2 = (10*d1 + d2) + (10*d3 + d4). Update minSum = min(minSum, sum2).
  • Return minSum.

Walkthrough

First, we extract the four digits from the input number num. Then, we generate all unique permutations of these four digits. For a number like 2932, the digits are 2, 2, 3, 9, and we would generate all 12 unique orderings. For each permutation, say (d1, d2, d3, d4), we consider all possible ways to split it into two non-empty numbers:

  1. new1 = d1, new2 = 100*d2 + 10*d3 + d4
  2. new1 = 10*d1 + d2, new2 = 10*d3 + d4

We calculate the sum new1 + new2 for each of these cases and keep track of the minimum sum found across all permutations and all splits. After checking everything, the minimum value we've recorded is the answer. Note that a split like (d1d2d3, d4) is covered by symmetry when another permutation is considered.

import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution {    public int minimumSum(int num) {        String s = Integer.toString(num);        List<Integer> digitList = new ArrayList<>();        for (char c : s.toCharArray()) {            digitList.add(c - '0');        }         Set<List<Integer>> permutations = new HashSet<>();        generatePermutations(digitList, 0, permutations);         int minSum = Integer.MAX_VALUE;         for (List<Integer> p : permutations) {            // Split 1: 1-digit and 3-digit            int n1_split1 = p.get(0);            int n2_split1 = p.get(1) * 100 + p.get(2) * 10 + p.get(3);            minSum = Math.min(minSum, n1_split1 + n2_split1);             // Split 2: 2-digit and 2-digit            int n1_split2 = p.get(0) * 10 + p.get(1);            int n2_split2 = p.get(2) * 10 + p.get(3);            minSum = Math.min(minSum, n1_split2 + n2_split2);        }        return minSum;    }     private void generatePermutations(List<Integer> arr, int k, Set<List<Integer>> permutations) {        if (k == arr.size()) {            permutations.add(new ArrayList<>(arr));            return;        }        for (int i = k; i < arr.size(); i++) {            Collections.swap(arr, i, k);            generatePermutations(arr, k + 1, permutations);            Collections.swap(arr, k, i); // backtrack        }    }}

Complexity

Time

O(1). The number of digits is fixed at 4. The number of unique permutations of 4 items is at most `4! = 24`. For each permutation, we perform a constant number of splits and calculations. Therefore, the total number of operations is constant and does not depend on the value of `num`.

Space

O(1). We need space to store the digits and the permutations. Since the number of digits is fixed at 4, the space required is also constant.

Trade-offs

Pros

  • Guaranteed to find the correct answer by checking all possibilities.

  • Conceptually straightforward, as it directly translates the problem of "finding the minimum over all possibilities" into code.

Cons

  • Highly inefficient in terms of the number of computations performed compared to a more insightful approach.

  • The implementation is more complex due to the need for a permutation generation algorithm.

  • Does not scale well if the number of digits were to increase.

Solutions

class Solution {public  int minimumSum(int num) {    int[] nums = new int[4];    for (int i = 0; num != 0; ++i) {      nums[i] = num % 10;      num /= 10;    }    Arrays.sort(nums);    return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem