2457. 美丽整数的最小增量

English Version

题目描述

给你两个正整数 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 变成一个美丽整数。

解法

方法一：贪心

我们定义函数 $f(x)$ 表示一个整数 $x$ 的每一位数字之和，那么题目要求的最小非负整数 $x$ 就是 $f(n + x) \leq target$ 的最小值。

初始化 $x = 0$，循环判断 $f(n+x)$ 是否大于 $target$，如果大于，此时 $n+x$ 的最低一位非 $0$ 的数要置为 $0$，而前一位要加 $1$，然后继续判断。

循环结束，返回 $x$ 即可。

时间复杂度 $O(\log^2 n)$。

Python3

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        def f(x):
            v = 0
            while x:
                v += x % 10
                x //= 10
            return v

        x = 0
        while f(n + x) > target:
            y = n + x
            p = 10
            while y % 10 == 0:
                y //= 10
                p *= 10
            x = (y // 10 + 1) * p - n
        return x

Java

class Solution {
    public long makeIntegerBeautiful(long n, int target) {
        long x = 0;
        while (f(n + x) > target) {
            long y = n + x;
            long p = 10;
            while (y % 10 == 0) {
                y /= 10;
                p *= 10;
            }
            x = (y / 10 + 1) * p - n;
        }
        return x;
    }

    private int f(long x) {
        int v = 0;
        while (x > 0) {
            v += x % 10;
            x /= 10;
        }
        return v;
    }
}

C++

using ll = long long;

class Solution {
public:
    long long makeIntegerBeautiful(long long n, int target) {
        auto f = [](ll x) {
            int v = 0;
            while (x) {
                v += x % 10;
                x /= 10;
            }
            return v;
        };
        ll x = 0;
        while (f(n + x) > target) {
            ll y = n + x;
            ll p = 10;
            while (y % 10 == 0) {
                y /= 10;
                p *= 10;
            }
            x = (y / 10 + 1) * p - n;
        }
        return x;
    }
};

Go

func makeIntegerBeautiful(n int64, target int) int64 {
	f := func(x int64) int {
		v := 0
		for x > 0 {
			v += int(x % 10)
			x /= 10
		}
		return v
	}
	var x int64
	for f(n+x) > target {
		y := n + x
		var p int64 = 10
		for y%10 == 0 {
			y /= 10
			p *= 10
		}
		x = (y/10+1)*p - n
	}
	return x
}

TypeScript

...