Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2578.html

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

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 {
        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];
        }
    };
    
  • 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)
    
    
  • 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 = new Array(10).fill(0);
        let n = 0;
        for (; num > 0; num = Math.floor(num / 10)) {
            ++cnt[num % 10];
            ++n;
        }
        const ans = new 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(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]
        }
    }
    

All Problems

All Solutions