What is the approach for solving the Minimum Addition to Make Integer Beautiful problem?

The approach involves examining each digit independently and using a greedy method to find the minimum x that makes the digit sum less than or equal to the target.

Why is the greedy method used in this problem?

The greedy approach works because it allows us to incrementally adjust each digit, ensuring the smallest necessary change to make the sum of digits meet the target.

What are the main pitfalls when solving this problem?

Common pitfalls include not accounting for each digit separately or not minimizing the addition required to make the sum of digits meet the target.

How does GhostInterview assist in solving this problem?

GhostInterview provides structured guidance on breaking down the problem, helping you understand the greedy approach and avoid common mistakes.

What is the time complexity of solving this problem?

The time complexity is O(d), where d is the number of digits in n. This is efficient due to the logarithmic nature of digit analysis.

#2457

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

美丽整数的最小增量

给你两个正整数 n 和 target 。如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个美丽整数。找出并返回满足 n + x 是美丽整数的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。示例 1：输入： n = 16, target =…

数学贪心

题目描述

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

lightbulb

解题思路

方法一：贪心

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

如果 $y = n+x$ 的每一位数字之和大于 $target$ ，那么我们可以循环通过以下操作，将 $y$ 的每一位数字之和减小到小于等于 $target$ ：

找到 $y$ 的最低位的非零数字，将其减小到 $0$ ，并将其高一位的数字加 $1$ ；
更新 $x$ ，继续上述操作，直到 $n+x$ 的每一位数字之和小于等于 $target$ 。

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

我们可以举个例子，假设 $n=467$ , $target=6$ ，那么 $n$ 的变化过程如下：

\begin{aligned} & 467 \rightarrow 470 \rightarrow 500 \\ \end{aligned}

时间复杂度 $O(\log^2 n)$ ，其中 $n$ 给题目给定的整数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

        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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Interviewee demonstrates understanding of digit-based greedy strategies.
question_mark
Candidate identifies the importance of considering each digit independently.
question_mark
Solver maintains efficiency with a logarithmic approach to the number of digits.

warning

常见陷阱

外企场景

error
Forgetting to consider the sum of digits at each place value independently.
error
Not minimizing the addition when examining possible values for x.
error
Misunderstanding the problem constraints and incorrectly assuming the addition could be larger.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the target were negative or zero?
arrow_right_alt
What if n is very large, approaching the upper limits of the constraint?
arrow_right_alt
What if the target was set to be much larger than the sum of digits of n?

help

常见问题

外企场景

继续练习

#2541 使数组中所有元素相等的最小操作数 II #2366 将数组排序的最少替换次数 #2358 分组的最大数量