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 ≤ 10.
PythonJavaC++GoTypeScriptRust
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)(code-box)
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];
}
}(code-box)
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];
}
};(code-box)
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]
}(code-box)
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];
}(code-box)
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]
}
}(code-box)
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 × log n), and the space complexity is O(n). Where n is the number of digits in num.
PythonJavaC++GoTypeScriptRust
class Solution:
def splitNum(self, num: int) -> int:
s = sorted(str(num))
return int(''.join(s[::2])) + int(''.join(s[1::2]))(code-box)
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];
}
}(code-box)
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];
}
};(code-box)
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]
}(code-box)
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];
}(code-box)
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]
}
}(code-box)
