Skip to main content
Talentd

Split With Minimum Sum - Solution & Explanation

EasyMathGreedySorting17 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.

The function minSum converts the integer to a string to easily sort the digits. By sorting the digits, the smallest values are handled first. It distributes the sorted digits between two numbers num1 and num2 alternately. This guarantees that both numbers are as small as possible for a minimal sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting algorithm.
Space Complexity: O(n) for storing the 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

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

Counting + Greedy—
Sorting + Greedy—

Detailed 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

Video Solution

Split With Minimum Sum || Addition Rule || Leetcode-2578 • Aryan Mittal • 1,574 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Split With Minimum Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Move Chips to The Same Position

Next

Minimum Sum of Values by Dividing Array