LeetCode每日一题(2457. Minimum Addition to Make Integer Beautiful)-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode每日一题(2457. Minimum Addition to Make Integer Beautiful)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

You are given two positive integers n and target.

An integer is considered beautiful if the sum of its digits is less than or equal to target.

Return the minimum non-negative integer x such that n + x is beautiful. The input will be generated such that it is always possible to make n beautiful.

Example 1:

Input: n = 16, target = 6
Output: 4

Explanation: Initially n is 16 and its digit sum is 1 + 6 = 7. After adding 4, n becomes 20 and digit sum becomes 2 + 0 = 2. It can be shown that we can not make n beautiful with adding non-negative integer less than 4.

Example 2:

Input: n = 467, target = 6
Output: 33

Explanation: Initially n is 467 and its digit sum is 4 + 6 + 7 = 17. After adding 33, n becomes 500 and digit sum becomes 5 + 0 + 0 = 5. It can be shown that we can not make n beautiful with adding non-negative integer less than 33.

Example 3:

Input: n = 1, target = 1
Output: 0

Explanation: Initially n is 1 and its digit sum is 1, which is already smaller than or equal to target.

Constraints:

1 <= n <= 1012
1 <= target <= 150
The input will be generated such that it is always possible to make n beautiful.

对于 n 中的任意一位数字 n[i], 要想通过加法使当前位变小，而且成本最低，一定是加到 10，使 n[i] = 0 并且 n[i-1] += 1, 也就是向前进一位，要想实现进位，当前位要加的数字就是 10 - n[i], 也就是 n[i]的 10 进制的补位, 实际这样的操作对于单个数字的加和的减少量是 10 - n[i] - 1, 之所以要减 1 是因为我们有一个进位操作，下一位增加了 1，最后将这些补位组合起来就是最终要加的数字。这里要注意如果对 n[0]做操作， n[0-1]会越界，我们要在前面插入一个 1文章来源地址https://www.toymoban.com/news/detail-415416.html


impl Solution {
    pub fn make_integer_beautiful(mut n: i64, target: i32) -> i64 {
        let mut digits = Vec::new();
        let mut digits_sum = 0;
        while n > 0 {
            digits_sum += n % 10;
            digits.push(n % 10);
            n /= 10;
        }
        let mut complements = Vec::new();
        let mut i = 0;
        let mut extra = 0;
        while i < digits.len() {
            if digits_sum <= target as i64 {
                break;
            }
            complements.push(10 - digits[i] - extra);
            digits_sum -= digits[i] + extra - 1;
            if i == digits.len() - 1 {
                digits.push(1);
                extra = 0;
            } else {
                extra = 1;
            }
            i += 1;
        }
        complements.into_iter().rev().fold(0, |mut s, d| {
            s *= 10;
            s += d;
            s
        })
    }
}