最小加法使整数变美:LeetCode 2457 进位枚举法解析与 Go 实现(codeforces-go 仓库题解)
最小加法使整数变美:LeetCode 2457 进位枚举法解析与 Go 实现(codeforces-go 仓库题解)
本文围绕力扣第 317 场周赛 C 题「Minimum Addition to Make Integer Beautiful」(最小加法使整数变美)展开,讲解如何通过「枚举进位位置 + 数位和判定」在 O(log²n) 时间内求出最小增量。读者将掌握该题的完整推导、Python/Go 参考实现,以及 codeforces-go 仓库中与之配套的题解源码、测试用例与自动化评测机制,可直接用于复现与实战。
问题定义与题意拆解
题目要求:给定正整数 n 与目标值 target,求最小的非负整数增量 x,使得 n + x 的数位和(各位数字之和)不超过 target。
在该仓库中,本题位于周赛目录 leetcode/weekly/317/c/,对应实现函数签名为:
func makeIntegerBeautiful(n int64, target int) int64
其中 n 使用 int64 承载(题目数据规模下安全),返回值为最小增量。仓库中的测试文件 c_test.go 给出了本题的原始题源链接注释(https://leetcode.cn/contest/weekly-contest-317/problems/minimum-addition-to-make-integer-beautiful/),即该题为力扣第 317 场周赛第三题。
几个直观例子:
| 输入 n | target | 最小增量 | 结果数 & 数位和 |
|---|---|---|---|
| 16 | 6 | 4 | 20,数位和 2 ≤ 6 |
| 467 | 6 | 33 | 500,数位和 5 ≤ 6 |
| 1 | 1 | 0 | 1,数位和 1 ≤ 1 |
| 55 | 1 | 45 | 100,数位和 1 ≤ 1 |
核心思路:不断 +1,直到产生进位
原文档给出的基本观察是:不断 +1 直到产生进位,数位和就可能变小。
原因在于数位和的变化规律:
- 普通加 1(无进位)时,个位数字变大 1,数位和严格增加 1;
- 一旦加 1 产生进位(如 9 → 10、99 → 100),低位一串 9 全部归零,数位和会骤降。
因此,最优解必然出现在某个「进位之后」的数上——即形如 ...999 → ...000 的进位结果。我们要做的,就是在每一个数位位置尝试「进一次位」,得到一个候选数 m,然后检查 m 的数位和是否已经不超过 target;从最低位到最高位依次尝试,第一个满足条件的 m 与 n 的差就是最小增量。
原文档以 n = 467 为例说明了进位枚举的全过程:
- 十位数进位:
467 → 470; - 百位数进位:
467 → 500; - 千位数进位:
467 → 1000(这一条在target = 1时尤为重要,因为只有数位和减到 1 才可能满足约束)。
进位位置公式推导:m = n + (tail - n % tail) % tail
设 tail = 1, 10, 100, ...(依次代表在个位、十位、百位……上产生进位)。把 n 对齐到「tail 的下一个倍数」即可得到进位后的数:
m = n + (tail - n % tail) % tail
公式含义分解如下:
n % tail是n的低位部分,即当前需要被清零的那几位数字;tail - n % tail是从n加到下一个tail倍数所需的最小增量;- 外层再取模
% tail是为了处理n % tail == 0的情况:此时n本身已经是tail的倍数(低位恰好全零),无需进位,m应保持等于n,候选数位和不发生变化,直接进入下一位尝试。
沿用 n = 467 验证:
tail = 1:m = 467,数位和 17 > 6;tail = 10:m = 467 + (10 - 7) = 470,数位和 11 > 6;tail = 100:m = 467 + (100 - 67) = 500,数位和 5 ≤ 6,返回500 - 467 = 33。
再验证 target = 1 的极端情形 n = 55:
tail = 1:m = 55,数位和 10 > 1;tail = 10:m = 60,数位和 6 > 1;tail = 100:m = 100,数位和 1 ≤ 1,返回100 - 55 = 45。
参考实现
Python3
class Solution:
def makeIntegerBeautiful(self, n: int, target: int) -> int:
tail = 1
while True:
m = x = n + (tail - n % tail) % tail # 进位后的数字
s = 0
while x:
s += x % 10
x //= 10
if s <= target:
return m - n
tail *= 10
Go
func makeIntegerBeautiful(n int64, target int) int64 {
for tail := int64(1); ; tail *= 10 {
m := n + (tail-n%tail)%tail // 进位后的数字
sum := 0
for x := m; x > 0; x /= 10 {
sum += int(x % 10)
}
if sum <= target {
return m - n
}
}
}
两份实现逻辑完全一致:外层循环枚举 tail(进位位置),内层循环累加 m 的数位和;一旦 sum <= target 立即返回增量 m - n。仓库中的对应源码为 c.go,函数实现与原文档中的 Go 代码逐行对应。
复杂度分析
- 时间复杂度:O(log² n)。外层循环最多尝试
log₁₀ n + 1个进位位置(从个位一直到多出的一位,如467 → 1000),每次循环计算数位和需要 O(log₁₀ n) 次除法与取模,故总量为 O(log² n); - 空间复杂度:O(1),仅用到
tail、m、sum等若干变量。
关于终止性:当 tail 增长到大于 n 时,m 必然成为下一个 10 的幂(如 1000),其数位和为 1,而题目保证 target >= 1,因此循环必然在某一步返回,不存在死循环。
仓库源码与自动化测试验证
该仓库围绕本题提供了完整的「题解源码 + 用例数据 + 自动化评测」三件套:
- c.go:函数实现本体;
- c.txt:手工整理的样例数据文件,每 3 行一组(输入
n、输入target、期望输出),共 4 组用例,内容与上文表格完全一致; - c_test.go:由模板 copypasta/template/leetcode/generator_test.go 生成的测试入口,调用 testutil.RunLeetCodeFuncWithFile 从
c.txt读取用例并自动比对结果; - 测试框架位于 leetcode/testutil/leetcode.go,
RunLeetCodeFuncWithFile会按「每NumIn + NumOut行一组」切分文本数据(leetcode/testutil/leetcode.go),再通过反射逐组调用被测函数并断言输出,同时内置超时检测(isTLE)与答案错误定位。
需要复现验证时,可在仓库根目录直接执行:
go test ./leetcode/weekly/317/c/
测试将通过 c.txt 中的 4 组数据自动校验上述全部示例输出(4、33、0、45),这也是把示例输入转成可直接回归的测试用例的标准做法。
边界情况与实战要点
n本身已满足条件:当n的数位和已经 ≤target时,tail = 1下m = n,直接返回m - n = 0,对应样例n = 1, target = 1 → 0;target = 1时必须跨位数进位:若n不以 9 结尾,个位进位通常无法把数位和降到 1,必须依次尝试十位、百位,直到进位出一个 10 的幂(数位和为 1)。这是原文档特别强调467 → 1000的原因,也是外层循环不设显式上界、靠tail持续乘 10 即可收敛的关键;- 类型选择:Go 实现中
n、m、tail均使用int64,累加数位和时用int转换,避免大数场景下的溢出风险;Python 实现则依赖大整数天然无溢出; - 正确性来源:候选只取「进位后」的数即可覆盖最优解——任何不含进位的增量都会使数位和单调上升,不可能优于同一位上的进位候选,这一性质保证了枚举的完备性。
综上,本题的精髓在于把「不断 +1 的朴素模拟」压缩为「最多 log₁₀ n 个进位位置的枚举」,配合数位和判定即可线性收敛到最小增量。配合仓库内现成的测试用例与评测框架,读者可以立即运行验证,并将该思路迁移到其他数位操作类问题(如数位和最小化、进位构造类题目)中。