Count Largest Group: Digit Sum Grouping

Count Largest Group is LeetCode problem 1399. Given an integer n, you group every number from 1 to n by the sum of its digits. Return the number of groups that have the largest size.

For example, with n = 13, the digit sums split the numbers into nine groups. Four of those groups have two members each, which is the largest size. So the answer is 4.

Why this problem matters

Count Largest Group is a clean exercise in two fundamental patterns: computing a derived key from each element and grouping by that key using a hash map. These patterns appear constantly in data processing, analytics, and interview problems. Once you can compute digit sums and group by them, you can apply the same structure to problems like Group Anagrams or frequency counting tasks.

The key insight

Every number has a digit sum, and you can use that digit sum as a hash map key to collect numbers into groups. Once all numbers are grouped, you scan the group sizes to find the maximum, then count how many groups match that maximum. The whole problem reduces to three familiar operations: transform, group, and aggregate.

The solution

from collections import Counter

def count_largest_group(n: int) -> int:
    groups = Counter()
    for i in range(1, n + 1):
        digit_sum = sum(int(d) for d in str(i))
        groups[digit_sum] += 1
    max_size = max(groups.values())
    return sum(1 for size in groups.values() if size == max_size)

Visual walkthrough

Complexity analysis

Each number from 1 to n has O(log n) digits, and computing its digit sum takes time proportional to the number of digits. The counter stores at most 9 * 9 = 81 possible digit sums (for numbers up to 10^9), but in general the number of distinct keys is bounded by the digit sum range. Space is O(n) in the worst case if you store group members, or O(log n) if you only store counts, since the number of distinct digit sums for numbers up to n is at most 9 * floor(log10(n) + 1).

The building blocks

1. Digit sum computation

Extracting individual digits and summing them is a micro-pattern that shows up in problems like Happy Number and Add Digits. You can do it with string conversion or with modular arithmetic:

def digit_sum(n: int) -> int:
    total = 0
    while n > 0:
        n, digit = divmod(n, 10)
        total += digit
    return total

Both approaches work. String conversion is shorter. Modular arithmetic avoids string allocation.

2. Group-by with hash map

The pattern of iterating over elements, computing a key, and grouping by that key is everywhere. In Python, collections.Counter handles the case where you only need counts. For full group membership, collections.defaultdict(list) is the standard tool.

from collections import defaultdict

groups = defaultdict(list)
for i in range(1, n + 1):
    key = digit_sum(i)
    groups[key].append(i)

3. Count by maximum

Finding the max of a collection and then counting how many elements match that max is a two-pass pattern. First pass finds the maximum. Second pass counts matches.

max_size = max(len(v) for v in groups.values())
result = sum(1 for v in groups.values() if len(v) == max_size)

You can also do this in a single pass by tracking both the current max and its count simultaneously.

Edge cases

• n = 1: Only one group (digit sum 1 with member [1]). The largest group has size 1, and there is exactly 1 such group. Answer: 1.
• n = 2: Two groups (digit sum 1: [1], digit sum 2: [2]). Both have size 1. Answer: 2.
• All single digits (n = 9): Nine groups, each with exactly one member. All groups tie at size 1. Answer: 9.
• Large n: The number of distinct digit sums grows slowly. For n = 10000, digit sums range from 1 to 36. The algorithm handles this efficiently since Counter operations are O(1) per insertion.

From understanding to recall

You now see the three-step structure: compute digit sums, group by them, and count the groups at the maximum size. Each step is a reusable building block that appears in many other problems. The challenge is not understanding it once, but being able to reproduce it quickly when you encounter a grouping problem under time pressure.

Spaced repetition helps bridge that gap. CodeBricks breaks the problem into its building blocks (digit extraction, hash map grouping, max-count aggregation) and drills each one separately. After a few review cycles, these pieces become automatic, and you can assemble them on the fly without hesitation.

Related posts

• Happy Number - Another digit-based computation problem that uses digit extraction as a core building block
• Add Digits - Summing digits repeatedly until a single digit remains, the same digit sum operation applied iteratively
• Excel Sheet Column Number - A different kind of digit-by-digit accumulation using positional values rather than digit sums