Count Largest Group

Count Largest Group

What is this problem about?

In the "Count Largest Group" problem, you are given an integer $n$. You group every integer from 1 to $n$ based on the sum of its digits. For example, 12 and 21 both belong to the same group because their digit sums are both 3. Your goal is to find how many groups have the largest number of members.

Why is this asked in interviews?

This "Easy" level question is a frequent flyer at companies like Meta and Google. It tests basic data structure usage (specifically Hash Maps or arrays for frequency counting) and the ability to perform multi-stage processing: first calculating a property, then grouping by it, and finally analyzing the group sizes.

Algorithmic pattern used

The pattern used here is Frequency Counting with a Hash Table (or a fixed-size array). Since the maximum digit sum for numbers up to 10,000 is small ($9 imes 4 = 36$), an array of size 40 is sufficient to store the counts of each digit sum. You iterate from 1 to $n$, calculate the digit sum for each, increment the corresponding index in your count array, and then find the maximum value in that array.

Example explanation

Let $n = 13$.

• Digit sums:
  • 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9
  • 10: 1, 11: 2, 12: 3, 13: 4
• Groups:
  • Sum 1: {1, 10} (Size 2)
  • Sum 2: {2, 11} (Size 2)
  • Sum 3: {3, 12} (Size 2)
  • Sum 4: {4, 13} (Size 2)
  • Sum 5-9: (Size 1)
• Largest size is 2. There are 4 groups with this size. Result: 4.

Common mistakes candidates make

One frequent mistake is returning the size of the largest group instead of the number of groups that have that size. Another mistake is using an unnecessarily complex sorting algorithm to find the maximum frequency when a single pass through the count array is enough.

Interview preparation tip

Always clarify the return type. "Count largest group" can be ambiguous—does it mean the size or the frequency of the size? Reading the problem carefully and confirming with the interviewer can save you from a major logic error.