2457-美丽整数的最小增量

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

基本思路是，不断 +1 直到产生进位，就可能让数位和变小。

代码实现时，可以直接计算每个数位进位后的结果。

比如 467，十位数进位为 470，百位数进位为 500，千位数进位为 1000（这一点在 target}=1 时尤为重要）。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
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
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
func makeIntegerBeautiful(n int64, target int) int64 {
	for tail := int64(1); ; tail *= 10 {
		m := n + (tail-n%tail)%tail // 进位后的数字
		sum := 0
		for x := m; x > 0; x /= 10 {
			sum += int(x % 10)
		}
		if sum <= target {
			return m - n
		}
	}
}

复杂度分析

  • 时间复杂度：O(\log^2 n)。
  • 空间复杂度：O(1)，仅用到若干变量。
 Comments
On this page
2457-美丽整数的最小增量