Count Largest Group — Solution in Python, Java & C++
Count Largest Group solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Largest Group is an easy coding problem on hash table and math, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Hash Table, Math
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Take every integer from 1 to n and group them by their digit sum — all numbers whose digits add to the same value land in the same group.
Return how many groups have the largest size.
Example 1
Input: n = 13
Output: 4
Explanation: The groups are [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. Four groups have size 2.
Example 2
Input: n = 2
Output: 2
Explanation: [1] and [2] both have size 1.
Example 3
Input: n = 24
Output: 5
Constraints
1 <= n <= 10000
Hints for Count Largest Group
Hint 1
The digit sum of a number below 10000 is at most 36, so there are very few groups.
Hint 2
Bucket the counts, then find the maximum bucket size.
Hint 3
Finally count how many buckets tie for that maximum.
How to solve Count Largest Group
The digit sum is a tiny key — at most 36 for n <= 10000 — so a plain counting array over digit sums is enough.
Approach
- For each
ifrom1ton, compute its digit sum by repeatedly takingi % 10and dividing by 10. - Increment the bucket for that digit sum.
- Find the largest bucket size, then count how many buckets equal it.
Why it works
Every number belongs to exactly one group, so the buckets partition 1..n and the largest bucket size is well defined. Counting ties requires a second pass (or tracking both values in one).
Complexity
- Time —
O(n log n) — digit extraction per number - Space —
O(1) — the digit-sum range is bounded
Pitfalls
- Starting the range at
0adds a phantom member to the digit-sum-0 group. - Resetting the tie counter only on a strict improvement matters — using
>=would count the maximum twice.
Reference solution
Python
def countLargestGroup(n: int) -> int:
buckets = {}
for i in range(1, n + 1):
s = 0
x = i
while x > 0:
s += x % 10
x //= 10
buckets[s] = buckets.get(s, 0) + 1
best = 0
groups = 0
for c in buckets.values():
if c > best:
best = c
groups = 1
elif c == best:
groups += 1
return groupsJava
public static int countLargestGroup(int n) {
int[] buckets = new int[50];
for (int i = 1; i <= n; i++) {
int s = 0, x = i;
while (x > 0) { s += x % 10; x /= 10; }
buckets[s]++;
}
int best = 0, groups = 0;
for (int c : buckets) {
if (c == 0) continue;
if (c > best) { best = c; groups = 1; }
else if (c == best) groups++;
}
return groups;
}C++
int countLargestGroup(int n) {
vector<int> buckets(50, 0);
for (int i = 1; i <= n; i++) {
int s = 0, x = i;
while (x > 0) { s += x % 10; x /= 10; }
buckets[s]++;
}
int best = 0, groups = 0;
for (int c : buckets) {
if (c == 0) continue;
if (c > best) { best = c; groups = 1; }
else if (c == best) groups++;
}
return groups;
}JavaScript
var countLargestGroup = function(n) {
const buckets = new Array(50).fill(0);
for (let i = 1; i <= n; i++) {
let s = 0, x = i;
while (x > 0) { s += x % 10; x = Math.floor(x / 10); }
buckets[s]++;
}
let best = 0, groups = 0;
for (let i = 0; i < buckets.length; i++) {
if (buckets[i] === 0) continue;
if (buckets[i] > best) { best = buckets[i]; groups = 1; }
else if (buckets[i] === best) groups++;
}
return groups;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets