题目
给你两个正整数 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^12
1 <= target <= 150
- 生成的输入保证总可以使
n
变成一个美丽整数。
解题
方法一:贪心 模拟进位
思路
一种朴素的想法是,把 n
慢慢累加,每次计算所有位的和(sum
),第一次 sum <= target
时返回新数减原数就行了。但数据范围比较大,这样做必定会超时。
但是我们发现 n
作为一个数只能增大不能缩小,那么让所有位的和(以下称为 sum
)变小的唯一方法就是 n
进位。
比如:n = 1234
,此时 sum = 10
,要让 sum
变小只能把 n + 6
这样 n
就变成了 1240
,sum = 7
成功变小了!
所以我们可以把 n
从低位到高位枚举放入数组中,每次模拟进位,一旦发现 sum <= target
就把数组构造回数字再减去原来的 n
就得到了 x
。
代码
class Solution {
static final int N = 100;
public long makeIntegerBeautiful(long _n, int target) {
int[] digits = new int[N];
int sum = 0, idx = 0, cnt = 0;
long n = _n;
while (n != 0) {
int d = (int) (n % 10);
sum += d;
digits[idx++] = d;
n /= 10;
++cnt;
}
if (sum <= target) return 0L;
for (int i = 0; i < cnt; ++i) {
sum = sum - digits[i] + 1;
digits[i] = 0;
++digits[i + 1];
if (i == cnt - 1) ++cnt;
if (sum <= target) break;
}
long x = 0L;
for (int i = cnt - 1; i >= 0; --i) {
x = x * 10 + digits[i];
}
return x - _n;
}
}
评论区