更新题目 1399. Count Largest Group

题目 lc1399 · 修改（rev 2） · cc · 2026-10-26 23:11
body

@@ -1,5 +1,12 @@
 ## 题目
 
-把 1 到 n 按「各位数字之和」分组，问大小最大的组有几个。
+给一个正整数 `n`。把 1 到 `n` 按「各位数字之和」（下面简称位数和）分组，位数和相同的数放进同一组。问大小最大的组一共有几个。
+
+LeetCode 的范围是 `1 <= n <= 10^4`。
+
+| 输入 | 输出 | 怎么来的 |
+| --- | --- | --- |
+| `13` | `4` | 分组是 [1, 10]、[2, 11]、[3, 12]、[4, 13]、[5]、[6]、[7]、[8]、[9]，最大的组大小是 2，有 4 个 |
+| `2` | `2` | [1]、[2] 两组，大小都是 1 |
 
 [LeetCode 原题](https://leetcode.com/problems/count-largest-group/)
@@ -9,9 +16,25 @@
 Visa OA（2026-03，CodeSignal，90 分钟两道纯 DP，楼主挂了）第二题：楼主用谐音写「原型力扣衣衫旧旧，但是范围大很多，暴力解会 timeout，input 范围比较接近力扣恶妻依旧」，读作原型是 1399、数据范围接近 2719（Count of Integers，数位 DP）。也就是说考的是这题的大数据版，要用数位 DP（digit DP），不能逐个数字去算位数和。同一场第一题是 [[q:lc474]] 改成「at least」的版本。
 
+OA 里 `n` 的具体上限、问的是不是和 1399 完全一样的统计，现在的正文里都没有，未核实。下面按「`n` 大到不能逐个枚举」来写，LeetCode 范围内的直接写法放在代码最后。
+
 ## 思路
 
-LeetCode 原题 n ≤ 10^4，逐个算位数和、用哈希表计数就行。
+`n <= 10^4` 时，对 1 到 `n` 每个数算位数和，用 `Counter` 数每个位数和出现几次，取最大的次数，再数有几个位数和等于它。`n` 大了就不行：2026-10-26 实测 `n = 10^7` 时逐个算要 4.66 秒。
 
-范围大到 10^18 时，用数位 DP：从高位往低位填数字，状态是（当前位、已经累积的位数和、前面是否都贴着 n 的上界），返回「各个位数和分别有多少个数」。位数和最多 9 × 18 = 162，所以状态数很小。算出每个位数和的计数后，取最大值、数有几组等于它。
+两种范围最后一步一样，要的都是一张表 `counts[s]`：1 到 `n` 里位数和为 `s` 的数有几个。位数和最多是 9 乘以 `n` 的位数，`n = 10^18` 时也只有 172 种取值，表很小。问题是怎样不枚举就算出它。
+
+> [!term] 数位 DP（digit DP）
+> 统计「0 到 `n` 里有多少个数满足某个只取决于各位数字的条件」的一类做法。从高位往低位一位一位填数字，按「前面填的是否和 `n` 一模一样」分情况。一旦某一位填得比 `n` 小，后面各位就能随便填，可以批量计数。常见写法是带 `(pos, sum, tight)` 三个参数的记忆化递归，tight 就是「前面是否和 `n` 一样」。
+
+把 0 到 `n` 的每个数都补前导 0 到和 `n` 一样长（`n = 13` 时，7 看成 `07`），从高位往低位和 `n` 逐位比，只有两种可能：
+
+1. 每一位都相同，也就是 `x = n`。
+2. 在某一位 `i` 第一次不同。因为 `x <= n`，这一位上 `x` 的数字 `d` 比 `n` 的小。`i` 之前和 `n` 完全相同，`i` 之后各位填 0 到 9 都不会超过 `n`。
+
+第一次不同的位置是唯一的，所以每个数恰好落在一种情况里，加起来不重不漏。第二种情况里，位数和等于 `n` 前 `i` 位的和（代码里的 `prefix_sum`）加 `d`，再加后面随便填的部分。随便填的部分只看长度，预先算一张表 `ways[k][t]`：`k` 位数字串（允许前导 0）里位数和为 `t` 的有几个。`ways[0] = [1]`（空串和为 0），每多一位，把上一行的每个和往后加 0 到 9。
+
+拿 `n = 13` 走一遍：第 0 位 `d` 只能取 0，后面 1 位随便填，就是 00 到 09，位数和 0 到 9 各加 1。第 1 位前面是 1，`d` 取 0 到 2，就是 10、11、12，位数和 1 到 3 各加 1。最后 13 自己让位数和 4 加 1。下标 0 那个 1 是数字 0，题目从 1 开始，要减掉。得到 `counts` 的前 10 项是 `[0, 2, 2, 2, 2, 1, 1, 1, 1, 1]`，最大是 2，有 4 个，和例子一致。
+
+> [!say] Since n is too large to enumerate, I count how many numbers up to n have each digit sum. Any number other than n first differs from n at some position where its digit is smaller, and every digit after that is free. So for each position and each smaller digit, I add a precomputed table of how many free suffixes have each digit sum. Then I take the largest count and see how many digit sums reach it.
 
 ## 代码
@@ -19,40 +42,85 @@
 ```python
 from collections import Counter
-from functools import lru_cache
+from typing import List
 
-def count_largest_group(n):
-    """数位 DP 版，n 可以很大"""
-    digits = list(map(int, str(n)))
 
-    @lru_cache(None)
-    def go(pos, s, tight):
-        if pos == len(digits):
-            return {s: 1}
-        out = Counter()
-        lim = digits[pos] if tight else 9
-        for d in range(lim + 1):
-            for k, v in go(pos + 1, s + d, tight and d == lim).items():
-                out[k] += v
-        return dict(out)
+def count_largest_group(n: int) -> int:
+    """Number of digit-sum groups of 1..n that have the largest size.
 
-    cnt = Counter(go(0, 0, True))
-    cnt[0] -= 1                        # 去掉 0 这个数
-    cnt = {k: v for k, v in cnt.items() if v > 0}
-    mx = max(cnt.values())
-    return sum(1 for v in cnt.values() if v == mx)
+    Works for very large n (digit DP). Returns 0 when n < 1, since there are no groups.
+    """
+    if n < 1:
+        return 0
+    group_sizes = [size for size in digit_sum_counts(n) if size > 0]
+    largest = max(group_sizes)
+    return group_sizes.count(largest)
+
+
+def digit_sum_counts(n: int) -> List[int]:
+    """counts[s] = how many integers in [1, n] have digit sum s. Requires n >= 0."""
+    digits = [int(c) for c in str(n)]
+    length = len(digits)
+    ways = free_suffix_counts(length)
+    counts = [0] * (9 * length + 1)
+
+    prefix_sum = 0                    # digit sum of the part that still equals n
+    for position, limit in enumerate(digits):
+        free_length = length - position - 1
+        for d in range(limit):        # place a digit smaller than n's digit here
+            for suffix_sum, count in enumerate(ways[free_length]):
+                counts[prefix_sum + d + suffix_sum] += count
+        prefix_sum += limit           # place n's own digit and stay on the bound
+    counts[prefix_sum] += 1           # n itself
+
+    counts[0] -= 1                    # the all-zero string is the number 0, not in [1, n]
+    return counts
+
+
+def free_suffix_counts(length: int) -> List[List[int]]:
+    """ways[k][s] = how many k-digit strings (leading zeros allowed) have digit sum s."""
+    ways = [[1]]                      # the empty string has digit sum 0
+    for k in range(1, length + 1):
+        previous = ways[-1]
+        current = [0] * (9 * k + 1)
+        for s, count in enumerate(previous):
+            for d in range(10):
+                current[s + d] += count
+        ways.append(current)
+    return ways
+
+
+def digit_sum(x: int) -> int:
+    """Sum of the decimal digits of a non-negative integer."""
+    total = 0
+    while x > 0:
+        x, last = divmod(x, 10)
+        total += last
+    return total
+
+
+def count_largest_group_small(n: int) -> int:
+    """LeetCode version (n <= 10^4): compute each number's digit sum one by one."""
+    if n < 1:
+        return 0
+    group_sizes = Counter(digit_sum(x) for x in range(1, n + 1))
+    largest = max(group_sizes.values())
+    return sum(1 for size in group_sizes.values() if size == largest)
 ```
 
-本机和暴力版对拍过若干个 n（1、2、13、24、99、100、1000、4567）。
+招聘方说代码写法也计分，所以拆成三个函数：`count_largest_group` 只管「取最大、数个数」，`digit_sum_counts` 只管按位分情况，`free_suffix_counts` 只管随便填的那张表，面试官问到哪一步可以单独指着一个函数讲。`n < 1` 时没有任何组，返回 0，不加这个判断 `max` 会收到空列表报 `ValueError`。个数再大也不用管溢出，Python 的 `int` 没有上限。`count_largest_group_small` 是 LeetCode 范围内的直接写法，也拿来对拍。
+
+2026-10-26 用 Python 3.13.17 跑过上面这段代码：
+
+- 两个例子：`n = 13` 得 4，`n = 2` 得 2。`n = 0` 得 0。
+- 和逐个算的版本对拍：`n` 从 1 到 20000 每个都比，全部一致。`n <= 3000` 时整张 `counts` 表也逐项比过，全部一致。另取 20001 到 300000 之间 30 个随机的 `n`，也全部一致。
+- 速度：`n = 10^7` 时逐个算 4.66 秒，数位 DP 0.17 毫秒。`n = 10^18` 用 0.76 毫秒。
 
 ## 复杂度
 
-状态数 O(位数 × 162 × 2)，每个状态试 10 个数字、合并最多 162 个键。
+记 `L` 为 `n` 的位数。`free_suffix_counts` 第 `k` 行有 `9k + 1` 个和，每个往后加 10 次，主循环 `L` 个位置、每个位置最多 9 个 `d`、每个 `d` 扫一行不超过 `9L` 项，时间都是 `O(L^2)`。空间 `O(L^2)`，存整张 `ways`。`n = 10^18` 时 `L = 19`，只有几万次加法，所以是毫秒级。
 
 ## 易错点
 
-- 计数从 1 开始，0 要去掉。
-- 楼主的大数据版具体问的可能不是「最大组的个数」，而是别的统计（比如某个位数和有多少个数），数位 DP 的框架一样，最后那步换掉就行。
-
-## 英文讲法
-
-> [!say] With n this large I can't enumerate numbers, so I run a digit DP over position, running digit sum and a tight flag, which gives how many numbers have each digit sum.
+- **忘了减掉 0**。补前导 0 后，全 0 串就是数字 0，会被算进位数和 0 那一组。只有所有组大小都是 1 时（`n` 在 1 到 9），多出的这一组才会让答案多 1。实测 `n = 1` 正确 1、忘减版 2，`n = 5` 正确 5、忘减版 6，`n = 13` 两版都给 4，所以只拿题目例子测发现不了。
+- **把「填 `n` 自己的数字」也当成后面随便填**。循环写成 `for d in range(limit + 1)`，`d == limit` 那一支后面的位其实还受 `n` 限制。实测 `n = 13`：第 0 位 `d = 1` 时把 10 到 19 都算进来，位数和 4 这一组被数成 4 个（正确是 4 和 13 两个），答案给 1，正确是 4。
+- **OA 问的统计可能和原题不同**【推断】。原帖说范围接近 LC 2719，2719 的具体题面云端未核实。如果 OA 问的是别的统计（比如区间内、位数和落在某个范围的数有几个，或者要求取模），`digit_sum_counts` 不用改，只换最后一步：区间 `[lo, hi]` 的表用 `digit_sum_counts(hi)` 逐项减 `digit_sum_counts(lo - 1)`（短的后面补 0），要取模就在最后取一次。
更新题目 1399. Count Largest Group

body

meta
