We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Largest Group

Number: 1500

Difficulty: Easy

Paid? No

Companies: Mercari

Problem Description

Given an integer n, group all numbers from 1 to n based on the sum of their digits. Determine how many groups have the maximum number of elements among all groups.

Key Insights

  • Use a hash table (or dictionary) to count the frequency of each group determined by the digit sum.
  • Calculate the digit sum for each number from 1 to n.
  • Identify the maximum frequency and then count how many groups have that frequency.

Space and Time Complexity

Time Complexity: O(n * d) per number, where d is the number of digits (d is constant relative to n) Space Complexity: O(n) in the worst case for storing group counts, though the number of unique digit sums is bounded by the digits range.

Solution

The problem is solved by iterating over every number from 1 to n, computing the sum of its digits, and using a hash table to record the frequency for each computed sum. After processing all numbers, determine the maximum frequency among all groups and then count how many groups have this frequency. Data structures used include a dictionary/hash table for mapping digit sums to their occurrence count. The core idea is a straightforward counting strategy with simple arithmetic for obtaining digit sums.

Code Solutions

def countLargestGroup(n):
    # Dictionary to store the frequency of each digit sum
    group_counts = {}
    for number in range(1, n + 1):
        # Compute sum of digits for current number
        digit_sum = sum(map(int, str(number)))
        group_counts[digit_sum] = group_counts.get(digit_sum, 0) + 1
    
    # Determine the maximum frequency among all groups
    max_count = max(group_counts.values())
    # Count the groups with the maximum frequency
    return list(group_counts.values()).count(max_count)

# Example usage:
print(countLargestGroup(13))  # Expected output: 4
print(countLargestGroup(2))   # Expected output: 2
← Back to All Questions