Description#
Given a positive integer num, split it into two non-negative integers num1 and num2 such that:
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:
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
| class Solution:
def splitNum(self, num: int) -> int:
cnt = Counter()
n = 0
while num:
cnt[num % 10] += 1
num //= 10
n += 1
ans = [0] * 2
j = 0
for i in range(n):
while cnt[j] == 0:
j += 1
cnt[j] -= 1
ans[i & 1] = ans[i & 1] * 10 + j
return sum(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int splitNum(int num) {
int[] cnt = new int[10];
int n = 0;
for (; num > 0; num /= 10) {
++cnt[num % 10];
++n;
}
int[] ans = new int[2];
for (int 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int splitNum(int num) {
int cnt[10]{};
int n = 0;
for (; num; num /= 10) {
++cnt[num % 10];
++n;
}
int ans[2]{};
for (int 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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];
}
|
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
| 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]
}
}
|
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
| class Solution:
def splitNum(self, num: int) -> int:
s = sorted(str(num))
return int(''.join(s[::2])) + int(''.join(s[1::2]))
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int splitNum(int num) {
char[] s = (num + "").toCharArray();
Arrays.sort(s);
int[] ans = new int[2];
for (int i = 0; i < s.length; ++i) {
ans[i & 1] = ans[i & 1] * 10 + s[i] - '0';
}
return ans[0] + ans[1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int splitNum(int num) {
string s = to_string(num);
sort(s.begin(), s.end());
int ans[2]{};
for (int i = 0; i < s.size(); ++i) {
ans[i & 1] = ans[i & 1] * 10 + s[i] - '0';
}
return ans[0] + ans[1];
}
};
|
1
2
3
4
5
6
7
8
9
| 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]
}
|
1
2
3
4
5
6
7
8
9
| 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];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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]
}
}
|
