Problem Informations

• Problem Index: 1399
• Problem Link: Count Largest Group
• Topics: Hash Table, Math

Problem Description

You are given an integer $n$.

Each number from $1$ to $n$ is grouped according to the sum of its digits.

Return the number of groups that have the largest size.

Example 1:

Input: n = 13
Output: 4
Explanation: 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
Explanation: There are 2 groups [1], [2] of size 1.

Constraints:

• $1 \leq n \leq 10^4$

Intuition

The problem involves grouping numbers based on the sum of their digits and identifying the number of groups that are of the largest size. Initially, it may seem complex due to the necessity of calculating digit sums for each number up to $n$. However, with a systematic approach, it becomes simpler. By calculating and grouping numbers based on their digit sums, we can easily track the frequency of each group size and determine which groups are the largest.

Approach

To solve this problem, the first step is to calculate the sum of the digits for each number from $1$ to $n$. We achieve this using a helper function, sumOfDigits, which iterates through each digit of a number, adds it to a cumulative sum, then moves to the next digit by integer division.

1. Digit Sum Calculation: For each number between 1 and $n$, calculate the sum of its digits using the sumOfDigits function. This function processes a number by repeatedly extracting its last digit (using modulus 10) and then removing that digit (using integer division by 10).

2. Grouping by Digit Sum: Use a map (digitSumCount) to count the frequency of each digit sum. The key is the digit sum, and the value is the frequency of numbers having that digit sum.

3. Determine Largest Group Size: Traverse the map to find the group size that occurs the most frequently. Initialize largestSize to zero and update it whenever a larger group size is found. Simultaneously, maintain a count, numberOfLargestGroups, of how many groups have this maximum size.

4. Result Calculation: After traversing the map, numberOfLargestGroups will contain the number of groups that have the largest size, which is the desired output.

This method efficiently groups numbers and tracks the sizes of each group, allowing for the determination of how many groups have the largest size without any unnecessary calculations.

Code

C++

class Solution {
private:
    // Helper function to calculate the sum of digits of a given number.
    int sumOfDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;  // Add the last digit to the sum.
            num /= 10;        // Remove the last digit.
        }
        return sum;
    }

public:
    // Main function to count the number of largest-sized groups.
    int countLargestGroup(int n) {
        int largestSize = 0;  // To track the size of the largest group.
        int numberOfLargestGroups = 0;  // To count groups that have the largest size.
        map<int, int> digitSumCount;  // Map to store the frequency of each digit sum.

        // Calculate the digit sum for each number and update the count.
        for (int i = 1; i <= n; ++i) {
            int digitSum = sumOfDigits(i);
            digitSumCount[digitSum]++;
        }

        // Iterate through the map to find the largest group size and count them.
        for (pair<int, int> group : digitSumCount) {
            if (group.second > largestSize) {
                largestSize = group.second;  // Update the largest size.
                numberOfLargestGroups = 1;   // Reset the count for largest size.
            } else if (group.second == largestSize) {
                numberOfLargestGroups++;     // Increment count if another largest group is found.
            }
        }

        return numberOfLargestGroups;
    }
};

Python

class Solution:

    # Helper function to calculate the sum of digits of a given number.
    def sumOfDigits(self, num):
        total = 0
        while num > 0:
            total += num % 10  # Add the last digit to the sum.
            num //= 10         # Remove the last digit.
        return total

    # Main function to count the number of largest-sized groups.
    def countLargestGroup(self, n):
        largestSize = 0  # To track the size of the largest group.
        numberOfLargestGroups = 0  # To count groups that have the largest size.
        
        digitSumCount = {}  # Dictionary to store the frequency of each digit sum.

        # Calculate the digit sum for each number and update the count.
        for i in range(1, n + 1):
            digitSum = self.sumOfDigits(i)
            if digitSum in digitSumCount:
                digitSumCount[digitSum] += 1
            else:
                digitSumCount[digitSum] = 1

        # Iterate through the dictionary to find the largest group size and count them.
        for count in digitSumCount.values():
            if count > largestSize:
                largestSize = count  # Update the largest size.
                numberOfLargestGroups = 1  # Reset the count for largest size.
            elif count == largestSize:
                numberOfLargestGroups += 1  # Increment count if another largest group is found.

        return numberOfLargestGroups

Complexity

• Time complexity: The function countLargestGroup iterates over each number from $1$ to $n$. For each number, it computes the sum of its digits using the sumOfDigits function. Calculating the sum of digits for a number has a time complexity of $O(\log_{10} m)$, where $m$ is the number. Since $m$ can be at most $n$, the time complexity for summing the digits of all numbers from $1$ to $n$ is $O(n \log_{10} n)$. Additionally, iterating over the map to determine the largest group size also takes linear time, i.e., $O(k)$, where $k$ is the number of distinct digit sums (at most $9 \times \log_{10} n$ for sums of large numbers). Therefore, the overall time complexity is $O(n \log n)$.

• Space complexity: The function uses a map to store the frequency of digit sums, which requires space proportional to the number of distinct digit sums. The maximum sum of digits for a number $n$ is $9 \times \log_{10} n$ (since each digit is at most 9), so the size of the map is at most $9 \times \log_{10} n$. Hence, the space complexity is $O(\log n)$.