【贪心, 模拟进位】美丽整数的最小增量【力扣第 317 场周赛】

题目

6222. 美丽整数的最小增量

---

给你两个正整数 n 和 target 。

如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个 美丽整数 。

找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

示例 1：

输入：n = 16, target = 6
输出：4
解释：最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4 之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。

示例 2：

输入：n = 467, target = 6
输出：33
解释：最初，n 是 467 ，且其每一位数字的和是 4 + 6 + 7 = 17 。在加 33 之后，n 变为 500 且每一位数字的和变成 5 + 0 + 0 = 5 。可以证明无法加上一个小于 33 的非负整数使 n 变成一个美丽整数。

示例 3：

输入：n = 1, target = 1
输出：0
解释：最初，n 是 1 ，且其每一位数字的和是 1 ，已经小于等于 target 。

提示：

• 1 <= n <= 10^12
• 1 <= target <= 150
• 生成的输入保证总可以使 n 变成一个美丽整数。

解题

方法一：贪心 模拟进位

思路

一种朴素的想法是，把 n 慢慢累加，每次计算所有位的和(sum)，第一次 sum <= target 时返回新数减原数就行了。但数据范围比较大，这样做必定会超时。

但是我们发现 n 作为一个数只能增大不能缩小，那么让所有位的和（以下称为 sum）变小的唯一方法就是 n 进位。
比如：n = 1234，此时 sum = 10，要让 sum 变小只能把 n + 6 这样 n 就变成了 1240，sum = 7 成功变小了！

所以我们可以把 n 从低位到高位枚举放入数组中，每次模拟进位，一旦发现 sum <= target 就把数组构造回数字再减去原来的 n 就得到了 x。

代码

class Solution {
    static final int N = 100;
    
    public long makeIntegerBeautiful(long _n, int target) {
        int[] digits = new int[N];
        int sum = 0, idx = 0, cnt = 0;
        long n = _n;
        while (n != 0) {
            int d = (int) (n % 10);
            sum += d;
            digits[idx++] = d;
            n /= 10;
            ++cnt;
        }
        if (sum <= target) return 0L;
        for (int i = 0; i < cnt; ++i) {
            sum = sum - digits[i] + 1;
            digits[i] = 0;
            ++digits[i + 1];
            if (i == cnt - 1) ++cnt;
            if (sum <= target) break;
        }
        long x = 0L;
        for (int i = cnt - 1; i >= 0; --i) {
            x = x * 10 + digits[i];
        }
        return x - _n;
    }
}