Question

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 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

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$.

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)

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];
  }
}

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];
  }
};

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]
}

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];
}

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$.

class Solution:
  def splitNum(self, num: int) -> int:
    s = sorted(str(num))
    return int(''.join(s[::2])) + int(''.join(s[1::2]))

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];
  }
}

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];
  }
};

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]
}

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];
}

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]
  }
}