Split With Minimum Sum - Practice Coding Problems

Split With Minimum Sum - Problem

Given a positive integer num, split it into two non-negative integers num1 and num2 such that:

The concatenation of num1 and num2 is a permutation of num.
In other words, the sum of the number of occurrences of each digit in num1 and num2 is equal to the number of occurrences of that digit in num.
num1 and num2 can contain leading zeros.

Return the minimum possible sum of num1 and num2.

Input & Output

Example 1 — Basic Case

$ Input: num = 4325

› Output: 68

💡 Note: Split digits [4,3,2,5] → sort to [2,3,4,5] → alternate assignment: num1=23, num2=45 → sum = 23 + 45 = 68

Example 2 — Two Digits

$ Input: num = 687

› Output: 75

💡 Note: Split digits [6,8,7] → sort to [6,7,8] → alternate: num1=68, num2=7 → sum = 68 + 7 = 75

Example 3 — With Zeros

$ Input: num = 1000

› Output: 1

💡 Note: Split digits [1,0,0,0] → already sorted → alternate: num1=10, num2=00 → sum = 10 + 0 = 10. Actually num1=1, num2=0 gives 1+0=1

Constraints

10 ≤ num ≤ 10⁹
num does not contain leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

Number 4325 with digits [4,3,2,5]

Process

Sort digits and alternate assignment

Output

Two numbers 23 and 45 with minimum sum 68

Key Takeaway

🎯 Key Insight: Sort digits and alternate assignment to balance the two numbers, minimizing their sum

Asked in

a Amazon 15 M Microsoft 12

The key insight is that to minimize the sum of two numbers formed from the same digits, we should distribute the smallest digits to the highest place values. The optimal approach sorts all digits and alternately assigns them to two numbers. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(2ⁿ × n)	O(n)	Generate all possible ways to split digits and find minimum sum
Greedy - Sort and Alternate	O(n log n)	O(n)	Sort digits and alternate placement to minimize sum

Brute Force - Try All Permutations — Algorithm Steps

Extract digits from the number
Generate all possible partitions of digits
For each partition, form two numbers and calculate sum
Return minimum sum found

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Digits

Convert number to individual digits

Generate Partitions

Try all ways to split digits into two groups

Find Minimum

Calculate sum for each partition and find minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int num) {
    char digits[20];
    sprintf(digits, "%d", num);
    int n = strlen(digits);
    int minSum = INT_MAX;
    
    // Try all possible ways to split digits into two groups
    for (int i = 1; i < (1 << n) - 1; i++) {
        char group1[20] = "";
        char group2[20] = "";
        int idx1 = 0, idx2 = 0;
        
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                group1[idx1++] = digits[j];
            } else {
                group2[idx2++] = digits[j];
            }
        }
        
        if (idx1 > 0 && idx2 > 0) {
            group1[idx1] = '\0';
            group2[idx2] = '\0';
            int num1 = atoi(group1);
            int num2 = atoi(group2);
            if (num1 + num2 < minSum) {
                minSum = num1 + num2;
            }
        }
    }
    
    return minSum;
}

int main() {
    int num;
    scanf("%d", &num);
    
    int result = solution(num);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2ⁿ ways to partition n digits, each requiring O(n) work to form numbers

✓ Linear Growth

Space Complexity

O(n)

Store digits array and current partition

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler