{x}
blog image

Count Largest Group

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 <= n <= 104

Solution Explanation: Counting Largest Groups

This problem asks to find the number of groups with the largest size, where each group contains numbers whose digit sums are equal.

Approach:

The solution employs a hash table (or an array in this case, since the maximum sum of digits is relatively small) to efficiently count the occurrences of each digit sum. The algorithm iterates through numbers 1 to n, calculates the sum of digits for each number, and updates the count in the hash table. Finally, it identifies the maximum count and determines how many groups share this maximum count.

Algorithm:

  1. Initialization:

    • Create a hash table (or an array cnt of size 40, sufficient to store counts for digit sums up to 36 (9+9+9+9 for a 4-digit number)). Initialize all counts to 0.
    • Initialize mx (maximum count) to 0 and ans (number of groups with the maximum count) to 0.

  2. Iteration:

    • Iterate through numbers from 1 to n.
    • For each number i:
      • Calculate the sum of its digits (s). This can be done efficiently using a loop that repeatedly takes the modulo 10 to get the last digit, adds it to the sum, and then performs integer division by 10 to remove the last digit.
      • Increment the count for s in the hash table: cnt[s]++.
      • Update mx and ans:
        • If cnt[s] is greater than mx, it becomes the new maximum count. Set mx to cnt[s] and ans to 1 (only one group with this maximum count so far).
        • If cnt[s] is equal to mx, increment ans because another group has the same maximum count.

  3. Return:

    • Return ans, the number of groups with the largest size.

Time and Space Complexity:

  • Time Complexity: O(n log n) - The dominant operation is iterating through numbers 1 to n. Calculating the sum of digits for each number takes O(log n) time in the worst case (for a number with many digits).
  • Space Complexity: O(1) - The hash table (or array) has a fixed size of 40, independent of the input n.

Code Examples:

The provided code examples in Python, Java, C++, Go, and TypeScript all implement this algorithm. They differ slightly in syntax and data structure usage but follow the same core logic. The use of an array instead of a more general hash map is justified because the range of possible digit sums is small and predictable, making an array more efficient in this specific case.