美丽整数的最小增量

难度: Medium

给你两个正整数 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¹²
1 <= target <= 150
生成的输入保证总可以使 n 变成一个美丽整数。

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        tail = 1
        while True:
            m = x = n + (tail - n % tail) % tail
            s = 0
            while x:
                s += x % 10
                x //= 10
            if s <= target:
                return m - n
            tail *= 10

Explain

这个题解利用了一个逐步增加整数的方法，以找到满足每一位上的数字之和小于等于target的最小整数。首先，我们初始化一个变量tail，代表当前考虑的数字位（从个位开始，逐步考虑十位、百位等）。对于每个tail，计算调整n到下一个以tail为单位的整数（即使n的当前tail位变为0）。然后计算这个新整数各位数字的和，检查是否小于等于target。如果是，就返回增加的量；如果不是，增加tail的位数，即从个位检查变为十位检查，继续尝试。这种方式可以快速找到最小的美丽整数。

时间复杂度: O(d^2)（d是n的位数）

空间复杂度: O(1)

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        tail = 1
        while True:
            # 计算使n的当前tail位变为0的下一个整数
            m = x = n + (tail - n % tail) % tail
            s = 0
            # 计算新整数x的各位数字之和
            while x:
                s += x % 10
                x //= 10
            # 检查数字之和是否小于等于target
            if s <= target:
                return m - n
            # 增加tail的位数，继续尝试
            tail *= 10

Explore

将`tail`从1开始并逐步乘以10增加位数的策略，是为了逐位地处理整数`n`，从最低位到最高位依次进行。每次增加`tail`的位数（即从个位到十位，再到百位等）允许算法按照十进制数的结构，逐步调整数字，使其成为美丽整数。这种步进方式能够确保每次调整的影响局限在当前考虑的位和更高的位，而不影响已经处理过的较低位，从而避免了多余的迭代和计算。效率上，这种方法可以快速地找到答案，因为它避免了对所有可能的数字进行全面的遍历，而是利用逐位检查的方式，一旦找到满足条件的整数即可停止。

在算法中，表达式`(tail - n % tail) % tail`用于计算从整数`n`到下一个在`tail`位上为0的整数所需要增加的最小值。这里，`n % tail`计算出`n`在当前`tail`位上的余数，`tail - n % tail`则给出使当前`tail`位变为0所需增加的差值。如果`n`已经是在当前`tail`位为0的数（即`n % tail == 0`），则`(tail - n % tail) % tail`计算结果为0，表示不需要增加。这个表达式确保了只修改当前`tail`位及以上的数字，而不影响更低的位，从而精确地控制数字的增加，使其变成一个大于等于`n`的新整数`m`，在`tail`位上为0。

如果`m`的位数非常大，计算其各位数字之和的效率可能会下降，因为需要逐个处理每一位数字。在每次迭代中，都需要对整数`m`进行分解并求和，这可能导致计算成本随数字的位数增加而增加。一种可能的优化方法是使用动态规划或者缓存之前计算过的结果。例如，可以记录下在某个特定的`tail`位之前的数字之和，然后在此基础上添加新的位的影响，这样可以减少重复的计算。此外，对于非常大的数字，可以考虑更高效的数位处理技术，比如并行处理或使用更快的算法来计算数字之和。