2457. Minimum Addition to Make Integer Beautiful
Description
You are given two positive integers n
and target
.
An integer is considered beautiful if the sum of its digits is less than or equal to target
.
Return the minimum non-negative integer x
such that n + x
is beautiful. The input will be generated such that it is always possible to make n
beautiful.
Example 1:
Input: n = 16, target = 6 Output: 4 Explanation: Initially n is 16 and its digit sum is 1 + 6 = 7. After adding 4, n becomes 20 and digit sum becomes 2 + 0 = 2. It can be shown that we can not make n beautiful with adding non-negative integer less than 4.
Example 2:
Input: n = 467, target = 6 Output: 33 Explanation: Initially n is 467 and its digit sum is 4 + 6 + 7 = 17. After adding 33, n becomes 500 and digit sum becomes 5 + 0 + 0 = 5. It can be shown that we can not make n beautiful with adding non-negative integer less than 33.
Example 3:
Input: n = 1, target = 1 Output: 0 Explanation: Initially n is 1 and its digit sum is 1, which is already smaller than or equal to target.
Constraints:
1 <= n <= 1012
1 <= target <= 150
- The input will be generated such that it is always possible to make
n
beautiful.
Solutions
Solution 1: Greedy Algorithm
We define a function $f(x)$ to represent the sum of the digits of an integer $x$. The problem is to find the minimum non-negative integer $x$ such that $f(n + x) \leq target$.
If the sum of the digits of $y = n+x$ is greater than $target$, we can loop through the following operations to reduce the sum of the digits of $y$ to less than or equal to $target$:
- Find the lowest non-zero digit of $y$, reduce it to $0$, and add $1$ to the digit one place higher;
- Update $x$ and continue the above operation until the sum of the digits of $n+x$ is less than or equal to $target$.
After the loop ends, return $x$.
For example, if $n=467$ and $target=6$, the change process of $n$ is as follows:
$$ \begin{aligned} & 467 \rightarrow 470 \rightarrow 500 \ \end{aligned} $$
The time complexity is $O(\log^2 n)$, where $n$ is the integer given in the problem. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|