#1399

Easy

LeetCode Problem Workspace

Count Largest Group

Count the number of groups with the largest size by summing digits of numbers from 1 to n using a hash table approach.

Problem Statement

Given an integer n, group all numbers from 1 to n by the sum of their digits. Each group contains numbers sharing the same digit sum, and the grouping uses basic arithmetic and hash table mapping for counting efficiently.

Return the number of groups that contain the largest number of elements. For example, if multiple groups have the maximum size, count all of them. This problem tests combining math operations with hash table usage to track and evaluate group sizes.

Examples

Example 1

Input: n = 13

Output: 4

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

There are 2 groups [1], [2] of size 1.

Constraints

1 <= n <= 104

Solution Approach

Compute Digit Sums

Iterate from 1 to n and calculate the sum of digits for each number. Use a simple loop or arithmetic to extract each digit efficiently.

Store Counts in Hash Table

Map each digit sum to its frequency in a hash table. Increment the count for each number's digit sum as you iterate, ensuring constant time insertion.

Identify Largest Groups

Find the maximum value in the hash table and count how many keys have this value. Return that count as the number of largest groups.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(\log n)

Time complexity is O(n \log n) because computing digit sums takes log n operations per number. Space complexity is O(\log n) for storing the hash table of digit sum counts, which grows with the number of possible digit sums.

What Interviewers Usually Probe

Checks if you understand digit sum computation and its connection to group formation.
Wants to see correct use of hash table to count frequencies efficiently.
Looks for awareness of edge cases, like multiple groups sharing the maximum size.

Common Pitfalls or Variants

Common pitfalls

Forgetting that multiple numbers can have the same digit sum leading to incorrect counts.
Assuming group sizes are always unique, missing ties for largest size.
Using arrays instead of a hash table, which increases complexity unnecessarily.

Follow-up variants

Find the largest group itself instead of counting how many share the size.
Compute groups based on product of digits rather than sum.
Allow numbers with leading zeros in digit sum calculation for extended variant.

FAQ

What pattern does Count Largest Group follow?

It follows the Hash Table plus Math pattern, where digit sums are calculated and stored for frequency counting.

Can n be very large in Count Largest Group?

Yes, up to 10^4, so efficient digit sum computation and hash table usage is important.

Why use a hash table instead of an array?

Because the digit sums may not be sequential, a hash table handles sparse keys efficiently for counting groups.

How do you handle multiple largest groups?

After finding the maximum frequency, count all digit sums in the hash table with that frequency and return the count.

What is the main failure mode in this problem?

Ignoring ties between groups or miscalculating digit sums leads to wrong counts of the largest groups.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def countLargestGroup(self, n: int) -> int:
        cnt = Counter()
        ans = mx = 0
        for i in range(1, n + 1):
            s = 0
            while i:
                s += i % 10
                i //= 10
            cnt[s] += 1
            if mx < cnt[s]:
                mx = cnt[s]
                ans = 1
            elif mx == cnt[s]:
                ans += 1
        return ans

Continue Practicing

#1442 count triplets that can form two arrays of equal xor #1512 number of good pairs #1248 count number of nice subarrays