LeetCode 1399 - Count Largest Group

The problem asks us to group all integers from 1 to n based on the sum of their digits. Every number belongs to exactly

leetcodeeasyhash-tablemathcounting

LeetCode Problem 1399

Difficulty: 🟢 Easy
Topics: Hash Table, Math, Counting

Solution

Problem Understanding

The problem asks us to group all integers from 1 to n based on the sum of their digits. Every number belongs to exactly one group, determined by adding together all of its decimal digits.

For example:

  • 14 has digit sum 1 + 4 = 5
  • 5 also has digit sum 5

So both numbers belong to the same group.

On the other hand:

  • 13 has digit sum 4
  • 3 has digit sum 3

So they belong to different groups.

After forming all groups, we must determine which group size is the largest. Then we return how many groups have that maximum size.

For example, if the groups have sizes:

2, 2, 2, 2, 1, 1, 1

then the maximum size is 2, and there are 4 groups with that size, so the answer is 4.

The input consists of a single integer n, where:

1 <= n <= 10^4

This constraint is relatively small. Even a straightforward solution that iterates through every number and computes digit sums individually will run comfortably within time limits.

The important part of the problem is correctly grouping numbers and tracking frequencies.

Some important edge cases include:

  • n = 1, where there is only one group.
  • Small values like n = 2, where every group has size 1.
  • Values where multiple groups tie for the largest size.
  • Values where only one group has the maximum size.
  • Numbers with multiple digits, where digit-sum computation must work correctly.

Because the upper bound is only 10^4, efficiency is not a major concern, but we should still design a clean and optimal counting solution.

Approaches

Brute Force Approach

The most direct approach is to explicitly build every group.

For every number from 1 to n:

  1. Compute the digit sum.
  2. Store the number inside a list corresponding to that digit sum.
  3. After processing all numbers, examine all groups.
  4. Find the maximum group size.
  5. Count how many groups have that size.

This approach is correct because every number is assigned to exactly one group based on its digit sum. After all numbers are processed, the grouping accurately reflects the problem definition.

However, storing every number inside lists is unnecessary. The problem only asks for the size of each group, not the actual contents.

Optimal Approach

Instead of storing full groups, we only store the count of how many numbers belong to each digit sum.

The key observation is that we never need the actual numbers after grouping them. We only care about:

  • how large each group is
  • how many groups share the maximum size

So we can use a hash map:

digit_sum -> frequency

For each number:

  1. Compute its digit sum.
  2. Increment the corresponding frequency.

After processing all numbers:

  1. Find the maximum frequency.
  2. Count how many frequencies equal that maximum.

This reduces memory usage and keeps the implementation simple.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × d) O(n) Stores full groups of numbers
Optimal O(n × d) O(1) Stores only group counts

Here, d represents the number of digits in a number. Since n <= 10^4, d is at most 5.

Algorithm Walkthrough

  1. Create a hash map to store group sizes.

The key will be the digit sum, and the value will be how many numbers belong to that group. 2. Iterate through every number from 1 to n.

Every number must be assigned to exactly one group. 3. Compute the digit sum of the current number.

Repeatedly extract the last digit using modulo % 10, add it to a running total, then remove the last digit using integer division // 10. 4. Increment the frequency for that digit sum.

If the digit sum has not appeared before, initialize its count to 0 first. 5. After processing all numbers, determine the largest group size.

This is simply the maximum value in the hash map. 6. Count how many groups have that maximum size.

Iterate through all frequencies and count how many equal the maximum. 7. Return the final count.

Why it works

Every number from 1 to n is assigned to exactly one group based on its digit sum. The hash map accurately records the size of every group because each occurrence increments the correct frequency exactly once.

Once all numbers are processed, the maximum frequency corresponds to the largest group size. Counting how many groups share this maximum gives the required answer.

Therefore, the algorithm always produces the correct result.

Python Solution

class Solution:
    def countLargestGroup(self, n: int) -> int:
        def digit_sum(num: int) -> int:
            total = 0

            while num > 0:
                total += num % 10
                num //= 10

            return total

        group_count = {}

        for num in range(1, n + 1):
            current_sum = digit_sum(num)

            if current_sum not in group_count:
                group_count[current_sum] = 0

            group_count[current_sum] += 1

        largest_size = max(group_count.values())

        answer = 0

        for size in group_count.values():
            if size == largest_size:
                answer += 1

        return answer

The implementation starts by defining a helper function called digit_sum. This function computes the sum of digits for a given number using repeated modulo and integer division operations.

Next, the dictionary group_count stores how many numbers belong to each digit-sum group.

The loop from 1 to n processes every number exactly once. For each number, we compute its digit sum and increment the corresponding frequency inside the dictionary.

After all numbers are processed, max(group_count.values()) finds the largest group size.

Finally, another loop counts how many groups have that size and returns the result.

The implementation directly follows the algorithm described earlier and uses only the information required by the problem.

Go Solution

func countLargestGroup(n int) int {
    digitSum := func(num int) int {
        total := 0

        for num > 0 {
            total += num % 10
            num /= 10
        }

        return total
    }

    groupCount := make(map[int]int)

    for num := 1; num <= n; num++ {
        currentSum := digitSum(num)
        groupCount[currentSum]++
    }

    largestSize := 0

    for _, size := range groupCount {
        if size > largestSize {
            largestSize = size
        }
    }

    answer := 0

    for _, size := range groupCount {
        if size == largestSize {
            answer++
        }
    }

    return answer
}

The Go implementation mirrors the Python solution closely.

The primary difference is that Go uses a map[int]int instead of a Python dictionary. Go maps automatically return the zero value for missing keys, so we can directly increment:

groupCount[currentSum]++

without checking whether the key already exists.

The digit-sum helper is implemented as an anonymous function assigned to digitSum.

Since all values are small and n <= 10^4, integer overflow is not a concern.

Worked Examples

Example 1

Input:

n = 13

We process every number from 1 to 13.

Number Digit Sum Group Counts After Processing
1 1 {1:1}
2 2 {1:1, 2:1}
3 3 {1:1, 2:1, 3:1}
4 4 {1:1, 2:1, 3:1, 4:1}
5 5 {1:1, 2:1, 3:1, 4:1, 5:1}
6 6 {1:1, 2:1, 3:1, 4:1, 5:1, 6:1}
7 7 {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1}
8 8 {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1}
9 9 {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1}
10 1 {1:2, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1}
11 2 {1:2, 2:2, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1}
12 3 {1:2, 2:2, 3:2, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1}
13 4 {1:2, 2:2, 3:2, 4:2, 5:1, 6:1, 7:1, 8:1, 9:1}

The largest group size is:

2

The groups with size 2 are:

1, 2, 3, 4

So the answer is:

4

Example 2

Input:

n = 2

Processing steps:

Number Digit Sum Group Counts
1 1 {1:1}
2 2 {1:1, 2:1}

The maximum group size is:

1

There are two groups with size 1.

So the answer is:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n × d) Each number requires digit-sum computation
Space O(1) Only a limited number of digit sums exist

The algorithm processes every number from 1 to n exactly once. For each number, digit-sum computation takes O(d) time, where d is the number of digits.

Since n <= 10^4, the maximum digit count is only 5, making the algorithm effectively linear.

The space complexity is technically constant because the maximum possible digit sum is very small. Even for 9999, the digit sum is only 36, so the number of groups remains bounded.

Test Cases

solution = Solution()

assert solution.countLargestGroup(1) == 1   # Single number
assert solution.countLargestGroup(2) == 2   # Two groups of equal size
assert solution.countLargestGroup(13) == 4  # Provided example
assert solution.countLargestGroup(15) == 6  # Multiple tied largest groups
assert solution.countLargestGroup(24) == 5  # Mid-range input
assert solution.countLargestGroup(9) == 9   # Every digit sum unique
assert solution.countLargestGroup(10) == 1  # Group with digit sum 1 becomes largest
assert solution.countLargestGroup(99) == 1  # Larger range with one dominant group
assert solution.countLargestGroup(10000) > 0  # Maximum constraint stress test
Test Why
n = 1 Smallest valid input
n = 2 Multiple groups tied at size 1
n = 13 Official example
n = 15 Several groups share maximum size
n = 24 General medium-sized case
n = 9 Every number has unique digit sum
n = 10 First repeated digit-sum group
n = 99 Larger grouping behavior
n = 10000 Maximum constraint stress test

Edge Cases

One important edge case is the smallest possible input, n = 1. In this scenario, there is only one number and therefore only one group. A buggy implementation might incorrectly initialize counters or fail when computing the maximum frequency. This implementation handles it naturally because the dictionary will contain exactly one entry with frequency 1.

Another important case occurs when every group has the same size, such as n = 2. Here, both groups contain exactly one element. Some implementations incorrectly return the size of the largest group instead of the number of groups having that size. This solution explicitly counts how many groups match the maximum frequency, so it returns the correct result.

A third edge case involves transitions across digit boundaries, such as moving from 9 to 10. The digit sum changes from 9 to 1, which means the implementation must correctly process multi-digit numbers. The helper function repeatedly extracts digits until the number becomes zero, so numbers with any number of digits are handled correctly.

Another subtle edge case is large values near the upper constraint, such as 10000. The implementation remains efficient because the digit-sum calculation for each number is very small, and the number of possible digit sums is tightly bounded. This prevents excessive memory growth or performance degradation.