1399. Count Largest Group

EasyHash TableMath

Problem Description

In this problem, you are given an integer n. Your task is to count how numbers from 1 to n can be grouped based on the sum of their digits. Then, you need to return the count of the groups with the largest size. A group's size is determined by how many numbers share the same digit sum. For example, if n is 13, the numbers 11 (1+1=2) and 20 (2+0=2) would belong to the same group with a digit sum of 2. If the group with a digit sum of 2 has the most numbers in it, you would include that in your count of the largest groups.

Intuition

To solve this problem, the approach is to create a map that will keep track of how many times each digit sum appears across the numbers from 1 to n. The key intuition is that instead of directly grouping numbers and then comparing sizes, we can efficiently tally counts for each possible digit sum using a map or dictionary.

Here's the process to arrive at the solution:

We iterate through all numbers from 1 to n.
For each number, we calculate the sum of its digits.
We record the digit sum in a counter (dictionary) by incrementing the corresponding digit sum's count.
As we update the counter, we also keep track of the maximum count (size of the largest group) encountered so far.
If we encounter a digit sum with a count higher than our current maximum, we update the maximum and reset our answer to 1 since we have found a larger group size.
If we encounter a digit sum with a count equal to the maximum, we increment our answer because this is another group of the same largest size.

The final answer is the count of digit sum groups/counts that equal the maximum size we found throughout the iteration.

The provided Python solution follows this intuition and keeps track of the digit sums using the Counter class from the collections module, offering a clean and efficient way to manage the counts.

Learn more about Math patterns.

Solution Approach

The solution uses a hash table and some basic arithmetic operations to solve the problem. Specifically, it employs a Counter object from Python's collections module, which is a subclass of dictionary designed to count hashable objects.

Here's a detailed walk-through of the implementation:

A Counter called cnt is initialized to store the frequency of each possible digit sum. It maps each sum to the number of times it has appeared.
Two variables, ans and mx, are initialized to 0. ans will store the final answer (the number of groups with the largest size), and mx will store the current maximum size encountered.
We iterate over every number from 1 to n inclusive, using a for loop.
Inside the loop, for each number i, we calculate the digit sum by repeatedly taking i % 10 (which gives the last digit) and adding it to an accumulator variable s. After each step, we update i to i // 10 which effectively removes the last digit from i. This process continues in a while loop until i becomes 0.
We then update the Counter cnt by incrementing the count for the computed digit sum s.
After updating cnt, we compare the updated count cnt[s] to the current mx. If the new count is greater, this means we have a new largest group size, so we update mx to cnt[s], and reset ans to 1 as this is the first group of this new size.
If the new count cnt[s] is equal to the current mx, then we have found another group of the current largest size, and we increment ans by 1.
After the loop has finished executing, the variable ans holds the number of groups that have the largest size, and we return this value.

Mathematically, given s as the sum of digits of a number i, the operation to update cnt can be represented as:

cnt[s] += 1

And the comparisons to determine if we found a new largest group size or another group of that size is:

if mx < cnt[s]:
    mx = cnt[s]
    ans = 1
elif mx == cnt[s]:
    ans += 1

The provided code efficiently calculates the required group sizes and finds the number of groups with the largest size, adhering to the solution approach described.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using n = 15 to illustrate the solution approach:

Initialize a Counter named cnt and two variables: ans set to 0 and mx also set to 0.
We begin to iterate from 1 to 15. Firstly, we take number 1, the sum of its digits is 1. We update cnt[1] to be 1. Since mx < cnt[1], mx is now set to 1 and ans is set to 1.
Next, we consider number 2, the sum of its digits is 2. We update cnt[2] to be 1. Now mx is still 1, but ans is now 2, as we have two groups (for digit sums 1 and 2) with the same size, 1.
This process continues for numbers 3, 4, 5, 6, 7, 8, and 9, each forming a new group of size 1. ans is now 9.
Number 10 has a digit sum of 1, updating cnt[1] to 2. Now mx < cnt[1], so we set mx to 2 and ans to 1, since we have found a larger group size (group of digit sum 1 is now the largest with size 2).
Numbers 11, 12, and 13 have digit sums of 2, 3, and 4 respectively:
- For 11, cnt[2] becomes 2, tying with the current maximum size. This increments ans to 2 because there's another group with the same size as the largest found so far.
- For 12, cnt[3] becomes 2, tying again, and ans goes up to 3.
- For 13, cnt[4] becomes 2, tying again, and ans goes up to 4.
For Number 14, the digit sum is 5, and updating cnt[5] to 2 ties with the current max; ans is incremented to 5.
For Number 15, the digit sum is 6, which also ties with the max after updating cnt[6] to 2; ans is incremented to 6.

After considering all numbers from 1 to 15, we find there are 6 groups tied for the largest size, which is 2. The groups are the digit sums of 1, 2, 3, 4, 5, and 6.

Therefore, the final answer that would be returned is 6, representing the count of the largest groups by digit sum from 1 to 15.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def countLargestGroup(self, n: int) -> int:
5        # Initialize a counter to keep track of the sum of digits
6        digit_sum_counter = Counter()
7        # Initialize variables to keep track of the maximum count and the number of groups with that count
8        max_count = 0
9        num_groups_with_max_count = 0
10
11        # Iterate over each integer from 1 to n
12        for i in range(1, n + 1):
13            sum_of_digits = 0
14            current_number = i
15            # Calculate the sum of the digits of the current number
16            while current_number:
17                sum_of_digits += current_number % 10
18                current_number //= 10
19            # Increment the count for the group represented by this sum of digits
20            digit_sum_counter[sum_of_digits] += 1
21          
22            # Update max_count and num_groups_with_max_count based on the current sums
23            if max_count < digit_sum_counter[sum_of_digits]:
24                max_count = digit_sum_counter[sum_of_digits]
25                num_groups_with_max_count = 1
26            elif max_count == digit_sum_counter[sum_of_digits]:
27                num_groups_with_max_count += 1
28      
29        # Return the number of groups that have the maximum size
30        return num_groups_with_max_count
31

1class Solution {
2    public int countLargestGroup(int n) {
3        // Initialize a count array to keep track of the frequency of sums.
4        int[] sumFrequency = new int[40]; // The maximum sum for n digits can be 9 * 4 = 36, thus 40 is safe.
5        int largestGroupSizeCount = 0; // This will hold the count of groups with the largest size.
6        int maxGroupSize = 0; // This will hold the maximum size of any group encountered.
7      
8        // Loop through each number from 1 to n.
9        for (int i = 1; i <= n; ++i) {
10            int sumOfDigits = 0; // This will hold the sum of digits of the current number.
11          
12            // Loop to calculate the sum of digits of the current number.
13            for (int x = i; x > 0; x /= 10) {
14                sumOfDigits += x % 10;
15            }
16          
17            // Increase the frequency count of the current sum.
18            ++sumFrequency[sumOfDigits];
19          
20            // If the current sum frequency is greater than the maxGroupSize, update maxGroupSize and reset largestGroupSizeCount.
21            if (maxGroupSize < sumFrequency[sumOfDigits]) {
22                maxGroupSize = sumFrequency[sumOfDigits];
23                largestGroupSizeCount = 1;
24            } else if (maxGroupSize == sumFrequency[sumOfDigits]) {
25                // If the current sum frequency is equal to the maxGroupSize, increment the count.
26                ++largestGroupSizeCount;
27            }
28        }
29      
30        // Return the count of the sums that have the largest group size.
31        return largestGroupSizeCount;
32    }
33}
34

1class Solution {
2public:
3    int countLargestGroup(int n) {
4        // Array to store counts of sum groups with a large enough size 
5        // to avoid the constant reallocation.
6        int sumCounts[40] = {};
7
8        // Variables to keep track of the largest group size and the
9        // number of groups with this size.
10        int largestGroupSizeCount = 0; 
11        int largestGroupSize = 0;
12
13        // Iterate over all numbers from 1 to n.
14        for (int i = 1; i <= n; ++i) {
15            int digitSum = 0; // This will hold the sum of the digits.
16
17            // Calculate the sum of digits of the current number.
18            for (int x = i; x; x /= 10) {
19                digitSum += x % 10;
20            }
21
22            // Increment the count of the found sum.
23            ++sumCounts[digitSum];
24
25            // If we've found a new maximum size for our digit groups.
26            if (largestGroupSize < sumCounts[digitSum]) {
27                largestGroupSize = sumCounts[digitSum]; // Update the largest group size.
28                largestGroupSizeCount = 1; // Reset the count to reflect this new largest group size.
29            } else if (largestGroupSize == sumCounts[digitSum]) {
30                // If this group size is the same as the current largest, increment the count.
31                ++largestGroupSizeCount;
32            }
33        }
34
35        // Return the number of groups that have the largest size.
36        return largestGroupSizeCount;
37    }
38};
39

1function countLargestGroup(n: number): number {
2    // Initialize an array to store the count of each sum of digits
3    const sumCounts: number[] = new Array(40).fill(0);
4    let maxCount = 0;   // Variable to keep track of the maximum count of any sum
5    let numMaxGroups = 0; // Variable to count how many groups have this maximum count
6
7    // Iterate over each number from 1 to n
8    for (let i = 1; i <= n; ++i) {
9        let sum = 0; // Variable to store sum of digits of the current number i
10        // Calculate the sum of digits of i
11        for (let x = i; x > 0; x = Math.floor(x / 10)) {
12            sum += x % 10;
13        }
14        // Increase the count of this sum in the 'sumCounts' array
15        sumCounts[sum]++;
16        // Check if the current sum has a new maximum count
17        if (maxCount < sumCounts[sum]) {
18            maxCount = sumCounts[sum]; // Update the max count
19            numMaxGroups = 1; // Reset the number of max groups as a new max is found
20        } else if (maxCount === sumCounts[sum]) {
21            // If the current sum is equal to the maximum count,
22            // increment the number of groups with max count
23            numMaxGroups++;
24        }
25    }
26    // Return the number of groups with the maximum count of sums
27    return numMaxGroups;
28}
29

Time and Space Complexity

The given Python code computes the size of the largest group of numbers based on the sum of the digits of each number from 1 to n.

Time Complexity:

To analyze the time complexity, let's examine the primary operations in the code:

The for loop runs from 1 to n which gives us O(n) complexity.
Inside the loop, we calculate the sum of digits of an integer i. Since in the worst case scenario integer i can have at most O(log n) digits (since every increase by an order of magnitude adds one digit), the inner while loop runs in O(log n) time for each number.
Updating the counter for sum s and comparing mx with cnt[s] for each number is done in constant time, O(1).

The overall time complexity is thus the product of the complexity of the outer loop and the inner while loop, which gives us O(n log n).

Space Complexity:

For space complexity, we need to consider:

The counter cnt will at most have an entry for each distinct sum of digits s that we can get from numbers 1 to n. In the worst case, this sum would not exceed 9 * log n (assuming each digit of a number n is 9). Therefore, the space complexity due to the cnt map is O(log n).
The variables s, i, mx, and ans use constant space O(1).

The space complexity of the algorithm is mainly determined by the cnt map. Hence, the overall space complexity is O(log n).

The code you provided is already efficient with respect to big-O notation, and any further optimization would depend on specific constraints or requirements of the problem not detailed here.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?

I don’t know