2578. Split With Minimum Sum
Description
Given a positive integer num
, split it into two non-negative integers num1
and num2
such that:
- The concatenation of
num1
andnum2
is a permutation ofnum
.- In other words, the sum of the number of occurrences of each digit in
num1
andnum2
is equal to the number of occurrences of that digit innum
.
- In other words, the sum of the number of occurrences of each digit in
num1
andnum2
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
andnum2
may differ from the order of occurrence ofnum
.
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
Solutions
Solution 1: 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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
Solution 2: 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$.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|