最小加法使整数变美:LeetCode 2457 进位枚举法解析与 Go 实现(codeforces-go 仓库题解)

原创2026-10-09 21:37:011,619 阅读
文章标签:开发工具

最小加法使整数变美: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

公式含义分解如下:

  1. n % tail 是 n 的低位部分,即当前需要被清零的那几位数字;
  2. tail - n % tail 是从 n 加到下一个 tail 倍数所需的最小增量;
  3. 外层再取模 % 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,因此循环必然在某一步返回,不存在死循环。

仓库源码与自动化测试验证

该仓库围绕本题提供了完整的「题解源码 + 用例数据 + 自动化评测」三件套:

需要复现验证时,可在仓库根目录直接执行:

go test ./leetcode/weekly/317/c/

测试将通过 c.txt 中的 4 组数据自动校验上述全部示例输出(4、33、0、45),这也是把示例输入转成可直接回归的测试用例的标准做法。

边界情况与实战要点

  1. n 本身已满足条件:当 n 的数位和已经 ≤ target 时,tail = 1 下 m = n,直接返回 m - n = 0,对应样例 n = 1, target = 1 → 0;
  2. target = 1 时必须跨位数进位:若 n 不以 9 结尾,个位进位通常无法把数位和降到 1,必须依次尝试十位、百位,直到进位出一个 10 的幂(数位和为 1)。这是原文档特别强调 467 → 1000 的原因,也是外层循环不设显式上界、靠 tail 持续乘 10 即可收敛的关键;
  3. 类型选择:Go 实现中 n、m、tail 均使用 int64,累加数位和时用 int 转换,避免大数场景下的溢出风险;Python 实现则依赖大整数天然无溢出;
  4. 正确性来源:候选只取「进位后」的数即可覆盖最优解——任何不含进位的增量都会使数位和单调上升,不可能优于同一位上的进位候选,这一性质保证了枚举的完备性。

综上,本题的精髓在于把「不断 +1 的朴素模拟」压缩为「最多 log₁₀ n 个进位位置的枚举」,配合数位和判定即可线性收敛到最小增量。配合仓库内现成的测试用例与评测框架,读者可以立即运行验证,并将该思路迁移到其他数位操作类问题(如数位和最小化、进位构造类题目)中。

登录后查看全文
codeforces-go