Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Split With Minimum Sum solution and explanation

EasyGreedyMathSorting5 min read74.0% acceptanceUpdated 9 Apr 2026
Asked atAmazonGoogle
Practise Split With Minimum Sum
6:42
Split With Minimum Sum || Addition Rule || Leetcode-2578Aryan Mittal · 6:42 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. Split With Minimum Sum || Addition Rule || Leetcode-2578Aryan Mittal · 6:42 · 1K views
  2. Leetcode Biweekly Contest 99 | 6312. Split With Minimum Sum | Python 3Bayu Aji · 2:13 · 1K views
  3. Split With Minimum Sum || leetcode Biweekly 99 || Leetcode easyBinaryMagic · 11:59 · 389 views
  4. 2578. Split With Minimum Sum (Leetcode Easy)Programming Live with Larry · 8:31 · 367 views
  5. 2578. Split With Minimum Sum - JAVA (Bi-Weekly Contest 99)Sourin Majumdar · 6:51 · 246 views
  6. [Leetcode Biweekly 99] Split With Minimum SumSandeep Kumar · 2:05 · 139 views
  7. Leetcode 2578 Split With Minimum SumAlgorithmicIQ · 18:18 · 134 views
  8. 2578. Split With Minimum Sum ||Biweekly Contest 99Code Coder · 5:06 · 78 views
  9. Split With Minimum Sum(2578) ,#BiweeklyContest99Surajit Roy_Roll-50 · 10:23 · 75 views
  10. 2578. Split With Minimum Sum | Leetcode | Biweekly contest 99 | Pythoncodingwithme · 4:27 · 65 views

The 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.

Notes:

  • It is guaranteed that num does not contain any leading zeros.
  • The order of occurrence of the digits in num1 and num2 may differ from the order of occurrence of num.

Example 1:

Input: num = 4325
Output: 59
Explanation: We can split 4325 so that num1 is 24 and num2 is 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.

Example 2:

Input: num = 687
Output: 75
Explanation: We can split 687 so that num1 is 68 and num2 is 7, which would give an optimal sum of 75.

Constraints:

  • 10 <= num <= 109

Approach overview

Problem Overview: You receive an integer num. Rearrange its digits to form two new integers such that their sum is as small as possible. Each digit must be used exactly once, and leading zeros are allowed.

Approach 1: Brute Force Digit Partitioning (O(n!))

The naive idea is to generate every permutation of the digits and split them into two numbers in all possible ways. For each configuration, compute the sum and track the minimum. This guarantees the optimal result but quickly becomes infeasible because permutations grow factorially with the number of digits. Even for 10 digits, the search space is massive. This approach mainly helps understand the problem structure but is never practical for real inputs.

Approach 2: Greedy Approach with Sorting (O(n log n))

The optimal observation comes from how place values affect the final sum. Smaller digits should appear in lower place values across both numbers. Start by extracting all digits from num, then sort them in ascending order using a sorting algorithm. Build two numbers by distributing digits alternately: append the smallest digit to the first number, the next to the second number, then repeat.

This greedy distribution keeps both numbers balanced in length and ensures that small digits occupy the most significant positions. If one number becomes significantly longer than the other, its place values grow and increase the sum. Alternating digits avoids that imbalance while preserving the smallest possible leading digits. The approach relies on simple arithmetic operations and sequential iteration over the sorted digit list.

From an algorithm perspective, this combines greedy reasoning with math operations on digits. Sorting dominates the runtime, giving a time complexity of O(n log n), where n is the number of digits. Only a few variables are used to construct the numbers, so the space complexity is O(1) ignoring the digit list.

Recommended for interviews: The greedy sorting approach is the expected solution. Interviewers want to see the insight that distributing the smallest digits across both numbers minimizes the total sum. Mentioning the brute force idea shows you considered the search space, but implementing the greedy strategy demonstrates algorithmic intuition and efficiency.

Approach 1: Greedy Approach with Sorting

In this approach, the digits of the number are sorted in ascending order. By alternating assignment of these sorted digits to two different numbers, num1 and num2, we can ensure that they have minimal possible values, and hence their sum is minimized. This is because smaller digits accumulate towards smaller numbers when sorted in ascending order, leading to a smaller total sum.

def min_sum(num):
    digits = sorted(str(num))
    num1, num2 = 0, 0
    for i, digit in enumerate(digits):
        if i % 2 == 0:
            num1 = num1 * 10 + int(digit)
        else:
            num2 = num2 * 10 + int(digit)
    return num1 + num2

num = 4325
print(min_sum(num))
import java.util.Arrays;

public class MinSum {
    public static int minSum(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        Arrays.sort(digits);

        int num1 = 0, num2 = 0;
        for (int i = 0; i < digits.length; i++) {
            if (i % 2 == 0) {
                num1 = num1 * 10 + (digits[i] - '0');
            } else {
                num2 = num2 * 10 + (digits[i] - '0');
            }
        }

        return num1 + num2;
    }

    public static void main(String[] args) {
        int num = 4325;
        System.out.println(minSum(num));
    }
}
#include <iostream>
#include <string>
#include <algorithm>

int minSum(int num) {
    std::string numStr = std::to_string(num);
    std::sort(numStr.begin(), numStr.end());

    int num1 = 0, num2 = 0;
    for (size_t i = 0; i < numStr.size(); ++i) {
        if (i % 2 == 0)
            num1 = num1 * 10 + (numStr[i] - '0');
        else
            num2 = num2 * 10 + (numStr[i] - '0');
    }

    return num1 + num2;
}

int main() {
    int num = 4325;
    std::cout << minSum(num) << std::endl;
    return 0;
}
function minSum(num) {
    let digits = String(num).split('').sort();
    let num1 = 0, num2 = 0;
    digits.forEach((digit, index) => {
        if (index % 2 === 0) {
            num1 = num1 * 10 + Number(digit);
        } else {
            num2 = num2 * 10 + Number(digit);
        }
    });
    return num1 + num2;
}

let num = 4325;
console.log(minSum(num));
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

int minSum(int num) {
    char numStr[11];
    sprintf(numStr, "%d", num);
    int n = strlen(numStr);
    qsort(numStr, n, sizeof(char), compare);

    int num1 = 0, num2 = 0;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0)
            num1 = num1 * 10 + (numStr[i] - '0');
        else
            num2 = num2 * 10 + (numStr[i] - '0');
    }

    return num1 + num2;
}

int main() {
    int num = 4325;
    printf("%d\n", minSum(num));
    return 0;
}
using System;

public class MinSum {
    public static int MinSumFunc(int num) {
        char[] digits = num.ToString().ToCharArray();
        Array.Sort(digits);

        int num1 = 0, num2 = 0;
        for (int i = 0; i < digits.Length; i++) {
            if (i % 2 == 0) {
                num1 = num1 * 10 + (digits[i] - '0');
            } else {
                num2 = num2 * 10 + (digits[i] - '0');
            }
        }

        return num1 + num2;
    }

    public static void Main() {
        int num = 4325;
        Console.WriteLine(MinSumFunc(num));
    }
}

In Python, the approach involves sorting the digit string and using loops to create and sum two numbers. Python's dynamic typing allows for direct manipulation of numbers and strings efficiently.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing sorted digits.

Try this approach in the editor

Approach 2: Counting + Greedy

First, we use a hash table or array cnt to count the occurrences of each digit in num, and use a variable n to record the number of digits in num.

Next, we enumerate all the digits i in nums, and alternately allocate the digits in cnt to num1 and num2 in ascending order, recording them in an array ans of length 2. Finally, we return the sum of the two numbers in ans.

The time complexity is O(n), and the space complexity is O(C). Where n is the number of digits in num; and C is the number of different digits in num, in this problem, C leq 10.

function splitNum(num: number): number {
    const cnt: number[] = Array(10).fill(0);
    let n = 0;
    for (; num > 0; num = Math.floor(num / 10)) {
        ++cnt[num % 10];
        ++n;
    }
    const ans: number[] = Array(2).fill(0);
    for (let i = 0, j = 0; i < n; ++i) {
        while (cnt[j] === 0) {
            ++j;
        }
        --cnt[j];
        ans[i & 1] = ans[i & 1] * 10 + j;
    }
    return ans[0] + ans[1];
}
func splitNum(num int) int {
	cnt := [10]int{}
	n := 0
	for ; num > 0; num /= 10 {
		cnt[num%10]++
		n++
	}
	ans := [2]int{}
	for i, j := 0, 0; i < n; i++ {
		for cnt[j] == 0 {
			j++
		}
		cnt[j]--
		ans[i&1] = ans[i&1]*10 + j
	}
	return ans[0] + ans[1]
}
impl Solution {
    pub fn split_num(mut num: i32) -> i32 {
        let mut cnt = vec![0; 10];
        let mut n = 0;

        while num != 0 {
            cnt[(num as usize) % 10] += 1;
            num /= 10;
            n += 1;
        }

        let mut ans = vec![0; 2];
        let mut j = 0;
        for i in 0..n {
            while cnt[j] == 0 {
                j += 1;
            }
            cnt[j] -= 1;

            ans[i & 1] = ans[i & 1] * 10 + (j as i32);
        }

        ans[0] + ans[1]
    }
}
Try this approach in the editor

Approach 3: Sorting + Greedy

We can convert num to a string or character array, then sort it, and then alternately allocate the digits in the sorted array to num1 and num2 in ascending order. Finally, we return the sum of num1 and num2.

The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of digits in num.

function splitNum(num: number): number {
    const s: string[] = String(num).split('');
    s.sort();
    const ans: number[] = Array(2).fill(0);
    for (let i = 0; i < s.length; ++i) {
        ans[i & 1] = ans[i & 1] * 10 + Number(s[i]);
    }
    return ans[0] + ans[1];
}
func splitNum(num int) int {
	s := []byte(strconv.Itoa(num))
	sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
	ans := [2]int{}
	for i, c := range s {
		ans[i&1] = ans[i&1]*10 + int(c-'0')
	}
	return ans[0] + ans[1]
}
impl Solution {
    pub fn split_num(num: i32) -> i32 {
        let mut s = num.to_string().into_bytes();
        s.sort_unstable();

        let mut ans = vec![0; 2];
        for (i, c) in s.iter().enumerate() {
            ans[i & 1] = ans[i & 1] * 10 + ((c - b'0') as i32);
        }

        ans[0] + ans[1]
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing sorted digits.

Counting + Greedy–
Sorting + Greedy–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force Digit PermutationsO(n!)O(n)Only for conceptual understanding or extremely small digit counts
Greedy with SortingO(n log n)O(1)General case and the standard interview solution
Greedy with Counting Sort (Digits 0-9)O(n)O(1)When optimizing further since digits range only from 0 to 9

Frequently asked questions

Is Split With Minimum Sum easy or hard?

Split With Minimum Sum is classified as an Easy problem. The main challenge is recognizing the greedy insight that distributing sorted digits between two numbers minimizes their total sum.

Split With Minimum Sum Python/Java solution

The Python or Java implementation extracts digits using modulo and division, sorts them, and alternately appends digits to two numbers using multiplication by 10. The same greedy logic works across C, C++, Java, Python, C#, and JavaScript.

How to solve Split With Minimum Sum in O(n)?

An O(n) approach is possible using counting sort because digits range from 0 to 9. Count the frequency of each digit, then distribute digits alternately between two numbers while iterating from smallest to largest digit. This avoids comparison sorting and keeps the complexity linear.

What is the best approach for Split With Minimum Sum?

The greedy sorting approach is the best solution. Extract the digits, sort them in ascending order, and build two numbers by alternately assigning digits. This keeps both numbers balanced and ensures the smallest digits occupy the highest place values. The overall complexity is O(n log n) due to sorting.

Is Split With Minimum Sum asked at Google/Amazon/Meta?

Problems based on digit manipulation, greedy distribution, and sorting frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying greedy reasoning and digit-processing pattern are common interview topics.

What data structure is used in Split With Minimum Sum?

The solution primarily uses a simple array or list to store extracted digits. After sorting the digits, two integer variables are built using arithmetic operations. No advanced data structures are required.

What is the time complexity of Split With Minimum Sum?

The optimal greedy solution runs in O(n log n) time because the digits must be sorted first. Constructing the two numbers afterward is a linear O(n) pass. Space complexity is O(1) excluding the temporary list of digits.

Comments

Next problem · similarPartition Equal Subset SumMedium
Now write it yourselfClose this page and solve Split With Minimum Sum in the editor, without looking.
Practise Split With Minimum Sum