Count Largest Group

Easy
492.

Count Largest Group

Count Largest Group is an easy coding problem on hash table and math, asked in Amazon and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    The digit sum of a number below 10000 is at most 36, so there are very few groups.

  2. Hint 2

    Bucket the counts, then find the maximum bucket size.

  3. 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

  1. For each i from 1 to n, compute its digit sum by repeatedly taking i % 10 and dividing by 10.
  2. Increment the bucket for that digit sum.
  3. 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 0 adds 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 groups

Java

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