Count Largest Group - Leetcode Solution

Problem:

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits.

Return how many groups have the largest size.

Example:

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.

Solution:

The main idea is to count the frequency of each sum of the digits and find the maximum frequency.

We can create a frequency dictionary and count the frequency of the sums of the digits.

Then, we can find the maximum frequency and count the number of groups that have that frequency.

The steps involved in the solution are:

1. Create a dictionary to store the frequency of each sum of digits.

2. Loop through numbers from 1 to n and calculate the sum of digits of each number.

3. Increment the frequency of the sum of digits in the dictionary.

4. Find the maximum frequency of the sums of digits.

5. Loop through the dictionary and count the number of groups that have the maximum frequency.

6. Return the count of groups with the maximum frequency.

The python implementation for the same is as follows:

class Solution:
    def countLargestGroup(self, n: int) -> int:
        # Create a dictionary to store the frequency of each sum of digits
        digit_sum_freq = {}

        # Loop through numbers from 1 to n and calculate the sum of digits of each number
        for i in range(1, n+1):
            digit_sum = sum([int(d) for d in str(i)])
            
            # Increment the frequency of the sum of digits in the dictionary
            if digit_sum in digit_sum_freq:
                digit_sum_freq[digit_sum] += 1
            else:
                digit_sum_freq[digit_sum] = 1

        # Find the maximum frequency of the sums of digits
        max_freq = max(digit_sum_freq.values())

        # Loop through the dictionary and count the number of groups that have the maximum frequency
        count = 0
        for freq in digit_sum_freq.values():
            if freq == max_freq:
                count += 1

        # Return the count of groups with the maximum frequency
        return count

Time Complexity: O(nlogn) as the time complexity of str() method is log(n) and we are using it inside a for loop from 1 to n

Space Complexity: O(n) as we are using a dictionary to store the frequency of sums of digits.

1