美文网首页
【算法题】2457. 美丽整数的最小增量

【算法题】2457. 美丽整数的最小增量

作者: 程序员小2 | 来源:发表于2023-03-29 21:59 被阅读0次

题目:

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

java代码:

class Solution {
  public static long makeIntegerBeautiful(long n, int target) {
        if(judge(n,target))
            return 0;
        long ans = 0;
        long i = 10;
        while(!judge(n,target)){
            //没增加时的 n
            long lastN = n;
            //每次将n进位
            n = (n/i + 1)*i;
            //进十位 => 进百位 =>进千位
            i = i*10;
            //增加的差值就是n-lastN
            ans +=  n-lastN;
        }
        return ans;
    }

    //判断一个数的所有位加起来是不是 <= target
    public static boolean judge(long x, int target){
        long sum = 0;
        while(x != 0){
            sum += x%10;
            x = x/10;
        }
        return sum<=target? true:false;
    }
}

相关文章

网友评论

      本文标题:【算法题】2457. 美丽整数的最小增量

      本文链接:https://www.haomeiwen.com/subject/lqhqddtx.html