Medium

题目描述

给你两个正整数 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 ，已经小于等于目标值。

提示：

  • 1 <= n <= 10^12
  • 1 <= target <= 150
  • 题目数据保证总是可以使 n 变美丽。

解题思路

这道题的核心思想是贪心策略：从右往左（从低位到高位）逐步将非零数字变为零，直到数位和满足要求。

具体思路如下：

  1. 计算当前数位和：首先检查 n 的数位和是否已经满足条件，如果满足直接返回 0。

  2. 贪心策略：如果不满足，我们需要通过加法使某些位变为 0 来减少数位和。关键观察是：要使一个位变为 0，我们需要让它"进位"。比如对于数字 467，要让个位的 7 变成 0，需要加 3 使其变为 470，然后十位变成 0 需要加 30，最终变成 500。

  3. 从右往左处理：

    • 保存原始的 n 值
    • 从最低位开始，如果当前位不为 0，就计算需要多少才能让这一位变成 0（即进位到下一位）
    • 更新 n 为进位后的值，继续检查数位和
    • 重复此过程直到数位和 ≤ target

  4. 计算结果：最终的 n 值减去原始值就是答案。

这种方法的时间复杂度是 O(log n)，因为最多需要处理 log₁₀(n) 个数位。

代码实现

class Solution {
public:
    long long makeIntegerBeautiful(long long n, int target) {
        long long original = n;
        
        auto digitSum = [](long long num) {
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        };
        
        if (digitSum(n) <= target) {
            return 0;
        }
        
        long long power = 1;
        while (digitSum(n) > target) {
            int lastDigit = n % 10;
            if (lastDigit > 0) {
                n = n / 10 + 1;
                power *= 10;
            } else {
                n /= 10;
                power *= 10;
            }
        }
        
        return n * power - original;
    }
};

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        original = n
        
        def digit_sum(num):
            return sum(int(digit) for digit in str(num))
        
        if digit_sum(n) <= target:
            return 0
        
        power = 1
        while digit_sum(n) > target:
            last_digit = n % 10
            if last_digit > 0:
                n = n // 10 + 1
                power *= 10
            else:
                n //= 10
                power *= 10
        
        return n * power - original

public class Solution {
    public long MakeIntegerBeautiful(long n, int target) {
        long original = n;
        
        int DigitSum(long num) {
            int sum = 0;
            while (num > 0) {
                sum += (int)(num % 10);
                num /= 10;
            }
            return sum;
        }
        
        if (DigitSum(n) <= target) {
            return 0;
        }
        
        long power = 1;
        while (DigitSum(n) > target) {
            int lastDigit = (int)(n % 10);
            if (lastDigit > 0) {
                n = n / 10 + 1;
                power *= 10;
            } else {
                n /= 10;
                power *= 10;
            }
        }
        
        return n * power - original;
    }
}

var makeIntegerBeautiful = function(n, target) {
    const original = n;
    
    const digitSum = (num) => {
        let sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        return sum;
    };
    
    if (digitSum(n) <= target) {
        return 0;
    }
    
    let power = 1;
    while (digitSum(n) > target) {
        const lastDigit = n % 10;
        if (lastDigit > 0) {
            n = Math.floor(n / 10) + 1;
            power *= 10;
        } else {
            n = Math.floor(n / 10);
            power *= 10;
        }
    }
    
    return n * power - original;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要处理的位数为 log₁₀(n)，每次处理需要计算数位和也是 O(log n)
空间复杂度O(1)只使用常数级别的额外空间

相关题目