Count Largest Group - Solution & Explanation
Problem Statement
You are given an integer n.
Each number from 1 to n is grouped according to the sum of its digits.
Return the number of groups that have the largest size.
Example 1:
Input: n = 13 Output: 4 Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.
Example 2:
Input: n = 2 Output: 2 Explanation: There are 2 groups [1], [2] of size 1.
Constraints:
1 <= n <= 104
Approach Overview
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 104 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.
Approach 1: Grouping by Digit Sum
This approach involves iterating over each number from 1 to n, calculating the sum of its digits, and then grouping these numbers based on their digit sum. We'll use a map (or dictionary) where the keys are the digit sums and the values are the counts of numbers that have those digit sums. Finally, we'll find the largest count and return the number of groups that have this largest count.
The number of digits in input numbers is at most 4 because n can be up to 10,000. Hence, the maximum possible digit sum is 9 + 9 + 9 + 9 = 36. We create an array count of size 37 to store frequencies of each possible digit sum (0 through 36). Then, we iterate over each number from 1 to n, compute its digit sum, and increment the corresponding count. Finally, we determine the maximum group size by iterating over this count array and count how many times this size appears.
Complexity
Time Complexity: O(n) because we iterate through numbers from 1 to n and perform a constant-time operation (calculating digit sum).
Space Complexity: O(1) because we only use a fixed size array.
Approach 2: Using an Array for Counting
By leveraging the fact that the maximum digit sum for any number from 1 to n is relatively small, we can efficiently use an array instead of a map. The array index corresponds to the digit sum, and the values represent the frequencies (counts) of the respective digit sums.
In this approach, we use an array sized according to the maximum possible digit sum, allowing us to track group sizes directly based on their corresponding digit sums. This is a more space-efficient solution compared to using a Hashtable.
Complexity
Time Complexity: O(n).
Space Complexity: O(1), as the count array is fixed in size (46).
Approach 3: Hash Table or Array
We note that the number does not exceed 10^4, so the sum of the digits also does not exceed 9 times 4 = 36. Therefore, we can use a hash table or an array of length 40, denoted as cnt, to count the number of each sum of digits, and use a variable mx to represent the maximum count of the sum of digits.
We enumerate each number in [1,..n], calculate its sum of digits s, then increment cnt[s] by 1. If mx < cnt[s], we update mx = cnt[s] and set ans to 1. If mx = cnt[s], we increment ans by 1.
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the given number.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Grouping by Digit Sum | Time Complexity: O(n) because we iterate through numbers from 1 to n and perform a constant-time operation (calculating digit sum). |
| Using an Array for Counting | Time Complexity: O(n). |
| Hash Table or Array | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Table Grouping by Digit Sum | O(n * d) | O(k) | General solution when digit-sum range is unknown or when using hash maps is more intuitive |
| Array Counting by Digit Sum | O(n * d) | O(1) | Best when the digit-sum range is small and predictable |
Video Solution
Count Largest Group | Simple Simulation | Dry Run | Leetcode 1399 | codestorywithMIK • codestorywithMIK • 6,986 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Largest Group easy or hard?
Count Largest Group Python/Java solution
How to solve Count Largest Group in O(n)?
What is the best approach for Count Largest Group?
Is Count Largest Group asked at Google/Amazon/Meta?
What data structure is used in Count Largest Group?
What is the time complexity of Count Largest Group?
Ready to solve this problem?
Practice Count Largest Group with our built-in code editor and test cases.
Practice on FleetCode