Python 2160.py
class Solution:
def minimumSum(self, num: int) -> int:
result = 9999
for p in permutations(str(num)):
pp = "".join(p)
result = min(result, int(pp[:1]) + int(pp[1:]))
result = min(result, int(pp[:2]) + int(pp[2:]))
result = min(result, int(pp[:3]) + int(pp[3:]))
return result
Difficulty
and has an acceptance rate of about 86% (200k+ submissions).
Typical patterns to solve this problem:
- Greedy
- Math
- Sorting
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a single method minimumSum. The method receives an integer num, treats its decimal representation as a collection of digits, and searches for the smallest possible sum that can be obtained by splitting a permutation of those digits into two non-empty parts. The algorithm enumerates every ordering of the digits, evaluates three possible split positions for each ordering, and keeps track of the minimal sum encountered.
Core Logic
The method begins by establishing a high initial value for the result.
result = 9999
This sentinel ensures that any legitimate sum computed later will replace it.
Next, the code generates all possible permutations of the digit characters of num. The permutations function from the standard library yields each distinct ordering as a tuple of characters.
for p in permutations(str(num)):
Inside the loop, the tuple p is reassembled into a plain string.
pp = "".join(p)
With the concatenated string pp in hand, the algorithm evaluates three split points: after the first digit, after the second digit, and after the third digit. For each split, it converts the left and right substrings to integers and computes their sum. The current minimal result is updated with the smaller of the existing result and the newly computed sum.
result = min(result, int(pp[:1]) + int(pp[1:]))
result = min(result, int(pp[:2]) + int(pp[2:]))
result = min(result, int(pp[:3]) + int(pp[3:]))
After all permutations have been processed, the method returns the smallest sum found.
return result
Edge Cases Handled
When the original number contains repeated digits, the permutation generator still produces each distinct ordering, and the repeated values do not affect the correctness of the minimum-sum calculation because every possible arrangement is examined.
If a permutation begins with a '0', the conversion int(pp[:k]) automatically discards the leading zero, allowing sums that involve numbers with fewer effective digits to be considered without raising errors.
The initialization of result to 9999 is deliberately larger than any sum that can arise from splitting a four-digit number, guaranteeing that the first computed sum will replace the sentinel value. This also safeguards the algorithm when the input number has fewer than four digits; the slicing operations still produce valid substrings, and the integer conversion of an empty string is avoided because the split positions are chosen only up to the length of the string.
Implicit Optimizations
The implementation avoids storing intermediate sums in a collection; instead, it updates the running minimum directly inside the permutation loop. This in-place reduction minimizes memory usage and eliminates the overhead of an additional data structure.
By using Python’s built-in min function with two arguments, the code leverages a highly optimized C implementation for the comparison, which is faster than a manual conditional check written in pure Python.
The three split evaluations are performed sequentially without redundant recomputation of substrings. Each slice operation extracts a contiguous segment of the string, and the integer conversion is applied only once per segment, reducing the number of parsing steps.
Overall, the method systematically explores the complete search space while keeping auxiliary state to a minimum, resulting in a concise and efficient solution for the problem scope.
ELI5 - Simplified Explanation
Imagine having a box filled with four numbered building blocks. The code starts by looking at every possible way to arrange these blocks in a line. Because there are different ways to put these blocks in order, the code explores all those patterns one by one.
Once it picks a specific order for the blocks, it tries to split them into two smaller groups. It looks at a few different spots where it could make a cut. For example, it might put one block in the first group and three in the second, or maybe two blocks in each group. When it knows which numbers are in each group, it adds those groups together to see what the total sum is.
While it does this for every possible arrangement and every possible way to split the numbers, it keeps a tiny notebook to remember the smallest sum it has found so far. Every time it finds a new way to split the blocks that results in a smaller total than what is written in the notebook, it erases the old number and writes down the new, smaller one. By the time it finishes playing with all the arrangements, the final number left in the notebook is the smallest one possible.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | Python | Java | ||||||||
| leetcode.ca | C++ | Python | Java | C | Go | Rust | TS | ||||
| Progiez | C++ | Python | Java | ||||||||
| github | black-shadows | C++ | |||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| lkwq007 | Python | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C, C++, Go, Java, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| lkwq007 | Python | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java |
Videos
Similar Problems
- problem 258: Add Digits
- problem 2535: Difference Between Element Sum and Digit Sum of an Array
- problem 2544: Alternating Digit Sum
Solved On The Same Day
- problem 1379: Find a Corresponding Node of a Binary Tree in a Clone of That Tree
- problem 1720: Decode XORed Array
- problem 2181: Merge Nodes in Between Zeros
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality