Domain 1EasyCORE

Count Largest Group

The problem requires us to group numbers from 1 to `n` based on the sum of their digits. We then need to determine how many groups have the largest size. The input is an integer `n`, and the output is an integer representing the count of the largest-sized groups.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1399. Count Largest Group

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 65.3%


Problem Breakdown

The problem requires us to group numbers from 1 to n based on the sum of their digits. We then need to determine how many groups have the largest size. The input is an integer n, and the output is an integer representing the count of the largest-sized groups.

Inputs:

  • An integer n (where 1 <= n <= 10^4).

Outputs:

  • An integer representing the number of groups with the largest size.

Implicit Constraints or Tricky Edge Cases:

  • The range of n is quite large, so an efficient solution is necessary.
  • Single-digit numbers will each form their own group since their digit sum is unique.
  • Numbers with the same digit sum will be grouped together.

Intuition

A brute-force approach would involve calculating the digit sum for each number from 1 to n, grouping them accordingly, and then counting the sizes of these groups. This approach would work but would be inefficient due to its O(n * d) time complexity, where d is the number of digits in the largest number (which can be up to 5 for n = 10^4).

The key insight is to use a dictionary to map each digit sum to a list of numbers that have that sum. This allows us to efficiently group numbers and determine the size of each group.

Approach

  1. Initialize an empty dictionary to store groups, where keys are digit sums and values are lists of numbers with those sums.
  2. Iterate through each number from 1 to n:
    • Calculate the sum of its digits.
    • Add the number to the corresponding list in the dictionary based on its digit sum.
  3. Determine the maximum size among all groups.
  4. Count how many groups have this maximum size.
  5. Return this count.

Complexity Analysis

  • Time Complexity: O(n * d), where n is the input number and d is the number of digits in the largest number (which is at most 5 for 10^4). This is because we iterate through each number and calculate its digit sum.
  • Space Complexity: O(n) for storing the groups in the dictionary.

Solution

def countLargestGroup(n: int) -> int:
    # Dictionary to store groups based on digit sums
    groups = {}
    
    # Function to calculate the sum of digits of a number
    def digit_sum(x):
        return sum(int(digit) for digit in str(x))
    
    # Group numbers by their digit sum
    for i in range(1, n + 1):
        ds = digit_sum(i)
        if ds not in groups:
            groups[ds] = []
        groups[ds].append(i)
    
    # Find the size of the largest group
    max_size = max(len(group) for group in groups.values())
    
    # Count how many groups have this maximum size
    count_max_groups = sum(1 for group in groups.values() if len(group) == max_size)
    
    return count_max_groups

Edge Cases Handled

  • Single-digit numbers: Each number forms its own group since their digit sums are unique.
  • Numbers with the same digit sum: These numbers are correctly grouped together.
  • Largest possible n (10^4): The solution efficiently handles the upper limit of the input size.