更新题目 拆成 4 的幂：最少拆几个
题目 visa-split-into-powers-of-four · 修改（rev 3） · · 2026-10-26 23:11
body
@@ -1,5 +1,7 @@ ## 题目 -给一个整数数组。对每个整数 x，求最小的正整数 k，使 x 能写成 k 个数之和：其中**一个**是 1、2 或 3，其余 k − 1 个都是 2 的偶数次方、但不含 2^0（也就是 4、16、64……，可以重复用）。做不到返回 -1。 +给一个整数数组。对每个整数 x，求最小的正整数 k，使 x 能写成 k 个数之和：其中**一个**是 1、2 或 3，其余 k − 1 个都是 2 的偶数次方、但不含 2^0（也就是 4、16、64……，可以重复用）。做不到返回 -1。题面没写整个数组的返回格式，下面按逐个求、返回等长数组写。 + +例子：x = 30 时，30 = 2 + 16 + 4 + 4 + 4，共 5 项，答案是 5。x = 8 时做不到，答案是 -1（原因见下一节）。 ## 面经里怎么考的 @@ -9,31 +11,93 @@ ## 思路 -2 的偶数次方去掉 1 以后就是 4 的幂：4、16、64……它们都是 4 的倍数。所以 x 减去那个 1、2 或 3（记作 r）之后剩下的 m 必须是 4 的倍数，r 只有一种取法（x 除以 4 余几就是几）；x 本身是 4 的倍数时没有合法的 r，返回 -1。 +2 的偶数次方写成 2^(2j)，也就是 4^j。题目去掉了 j = 0（即 2^0 = 1），所以能用的数正好是 4 的正整数次幂：4、16、64……下面把那一项 1、2 或 3 叫做「小项」，记作 r，把 x 减去小项以后剩下的部分记作 m = x − r。 -剩下的 m 要用最少个数的 4 的幂凑出来。把 m 写成 4 进制，每一位上的数字就是要用几个对应的幂；4 进制各位数字之和就是最少个数（如果某一位用了 4 个以上，四个合成一个更高的幂会更少，所以 4 进制写法已经最省）。答案是 1 加上这个数位和。 +小项只有一种取法。4、16、64 都是 4 的倍数，它们的和 m 也一定是 4 的倍数（m = 0 也算，这时 k − 1 = 0）。m = x − r 是 4 的倍数，等价于 r 和 x 除以 4 的余数相同。r 只能在 1、2、3 里选，所以 r 就是 `x % 4`。由此得到两种无解的情况： + +- x 是 4 的倍数时，余数是 0，1、2、3 里没有合法的小项，返回 -1。比如 x = 8，减 1、2、3 分别剩 7、6、5，都不是 4 的倍数。 +- x ≤ 0 时，k 项都是正数，和不可能 ≤ 0，返回 -1。 + +x 是 1、2、3 时，m = 0，只用小项一项，答案是 1。 + +> [!say] Every allowed power is a power of four, so they all sum to a multiple of four. That forces the small term to be x mod 4, and if x itself is a multiple of four there is no valid small term, so the answer is minus one. + +剩下的 m 用最少几个 4 的幂凑出来，答案是 m 的 4 进制各位数字之和。把 m 写成 4 进制，第 j 位的数字 d_j 表示用 d_j 个 4^j，这样凑出来的个数就是各位数字之和。它是最少的，推导分两步： + +1. 任取一种凑法，如果某个 4^j 用了 4 个或更多，把其中 4 个换成 1 个 4^(j+1)，和不变、个数少 3。反复换下去个数一直变少，所以最少的凑法里每个 4^j 最多用 3 个。 +2. 每个 4^j 最多用 3 个的凑法，就是 m 的 4 进制写法，而一个数的 4 进制写法只有一种。所以最少的凑法只能是 4 进制写法。 + +m 是 4 的倍数，4 进制最低位（4^0 那一位）一定是 0，正好对上「不能用 1」这条限制。 + +例子：x = 30，30 % 4 = 2，小项取 2，m = 28。28 = 1 × 16 + 3 × 4 + 0 × 1，4 进制是 130，数字和 1 + 3 + 0 = 4，答案 1 + 4 = 5，和题目一节的拆法一致。 + +> [!say] For the remaining part, the fewest powers of four that add up to m is the digit sum of m in base four. If any power were used four or more times, I could merge four copies into the next power and save three terms, so an optimal answer uses each power at most three times, which is exactly the base-four representation. ## 代码 ```python -def min_parts(x): - for r in (1, 2, 3): - m = x - r - if m >= 0 and m % 4 == 0: - k = 1 # r 自己算一个 - while m: - k += m % 4 # 4 进制的每一位 - m //= 4 - return k - return -1 +from __future__ import annotations # 让 list[int] 这种注解在 Python 3.8 及以下也能用 + + +def base4_digit_sum(m: int) -> int: + """m >= 0，返回 m 写成 4 进制后各位数字之和。""" + total = 0 + while m > 0: + m, digit = divmod(m, 4) + total += digit + return total + + +def min_parts(x: int) -> int: + """x 最少拆成几项（一项取 1、2、3，其余取 4 的正整数次幂），做不到返回 -1。""" + if x <= 0: + return -1 # 每一项都是正数，和不可能 <= 0 + small = x % 4 # 那一项 1、2、3 只能取 x 除以 4 的余数 + if small == 0: + return -1 # x 是 4 的倍数：没有合法的那一项 + return 1 + base4_digit_sum(x - small) + + +def solve(nums: list[int]) -> list[int]: + """对数组里每个数分别求答案，返回等长数组。""" + return [min_parts(x) for x in nums] ``` -本机和暴力搜索在 1 到 299 上对拍过。 +Python 的整数不会溢出，x 很大时也不用特殊处理。 + +> [!optional] 用 Java 或 C++ 写时，x 超过 2^31 − 1 就要用 64 位整数（`long` / `long long`）。 + +2026-10-26 在云端用 python3 跑了三组，代码和上面逐字一致： + +- **和暴力对拍**：暴力解是完全背包（硬币取 4、16、64……求凑出 x − r 的最少硬币数，再枚举 r = 1、2、3），不复用 4 进制的推导。x 取 -5 到 2000 共 2006 个值，`min_parts` 和暴力全部一致。 +- **一种错误写法对照**：把「4 进制各位数字之和」写成「4 进制非零位的个数」，也就是把 2 × 4 当成一项。错误写法只换掉 `base4_digit_sum`，`min_parts` 其余部分不变： + + ```python + def base4_digit_sum(m: int) -> int: # 错误写法：数的是非零位的个数 + count = 0 + while m > 0: + m, digit = divmod(m, 4) + if digit != 0: + count += 1 + return count + ``` + + 同一组输入的结果： + + | x | 1 | 4 | 5 | 9 | 13 | 30 | 47 | 63 | 0 | -3 | + | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | + | 错误写法 | 1 | -1 | 2 | 2 | 2 | 3 | 3 | 3 | -1 | -1 | + | 正确写法 | 1 | -1 | 2 | 3 | 4 | 5 | 6 | 7 | -1 | -1 | + | 暴力 | 1 | -1 | 2 | 3 | 4 | 5 | 6 | 7 | -1 | -1 | + + x = 9 时 m = 8，4 进制是 20，非零位只有 1 个，错误写法得 2。可是 8 本身不是 4 的幂，要写成 4 + 4，正确答案是 1 + 2 = 3。在 -5 到 2000 上，错误写法有 1404 个值和暴力不一致。 +- **大输入**：`min_parts(10**18 + 1)` 返回 38，单次调用约 2 微秒（重复调用 10 万次取平均）。`min_parts(4**31 - 1)` 返回 91（m 的 4 进制是 30 个 3 后面跟一个 0）。 + +## 复杂度 + +每个数 x 的循环次数等于 m 的 4 进制位数，约 log₄ x，时间 O(log x)，额外空间 O(1)。整个数组是 O(n log X)，X 是数组里的最大值。 ## 易错点 -- 「2 的偶数次方」不含 2^0 = 1，所以只能是 4 的幂；看清这一句题就简单了。 -- 题面没说 4 的幂能不能重复用，上面按可以重复写；不能重复时，4 进制某位大于 1 就无解。 - -## 英文讲法 - -> [!say] Every allowed power is a power of four, so x minus the small term must be a multiple of four, and the fewest powers of four that sum to m is just the digit sum of m in base four. +- 「2 的偶数次方」不含 2^0 = 1，所以能用的只有 4 的幂。看清这一句，题就变成了上面的取余加数位和（见思路一节第一段）。 +- 答案按 4 进制各位数字之和算。只数非零位会少算，因为一位上的 2 或 3 代表要用 2 个或 3 个同样的幂（见代码一节的对照表）。 +- 题面没说 4 的幂能不能重复用，上面按可以重复写。如果不能重复，m 的 4 进制某一位大于 1 就无解，答案改成「有某位 ≥ 2 时返回 -1，否则 1 加非零位个数」（2026-10-26 和穷举所有子集的暴力在 -3 到 1499 上对拍过，全部一致）。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-1620", + "rewritten_at": "2026-10-27" +}