Count Largest Group - Video Solutions

Problem Overview: You receive an integer n. For every number from 1 to n, compute the sum of its digits and group numbers that share the same digit sum. The task is to determine how many groups end up with the maximum size.

The key observation is that the digit sum acts as a natural grouping key. Once you count how many numbers fall into each digit-sum bucket, the rest of the problem reduces to identifying the largest bucket size and counting how many buckets reach that size.

Approach 1: Grouping by Digit Sum using Hash Table (O(n * d) time, O(k) space)

Iterate through every integer from 1 to n. For each number, compute its digit sum by repeatedly taking num % 10 and dividing by 10. Use a hash table where the key is the digit sum and the value is the count of numbers that produce that sum. Each iteration performs constant work plus digit extraction, so the complexity is O(n * d), where d is the number of digits in n. After filling the map, scan the values to find the maximum frequency and count how many entries match it.

This approach is intuitive and flexible. A hash map handles any digit-sum range without precomputing limits, which keeps the logic straightforward.

Approach 2: Using an Array for Counting (O(n * d) time, O(1) space)

Instead of a hash table, use a fixed-size array where the index represents the digit sum. For typical constraints, the maximum digit sum for numbers up to 10⁴ is small (for example, 9999 → 36). That means you can allocate an array of size ~40 and use it as a counting bucket. For each number from 1 to n, compute its digit sum and increment count[sum]. After processing all numbers, iterate over the array to determine the largest frequency and count how many sums achieve it.

This version replaces hash lookups with direct indexing, which reduces overhead and keeps memory usage constant. The logic relies on simple math operations for digit extraction and works efficiently even for the upper bound of n.

Recommended for interviews: The counting-array approach is usually the best answer. It shows that you recognized the limited range of digit sums and optimized the data structure choice. Starting with the hash table version demonstrates clear thinking about grouping, while the array optimization shows deeper understanding of constraints and constant-space techniques.