LeetCode 1399. Count Largest Group

Description

https://leetcode.com/problems/count-largest-group/

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 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.

Example 3:

Input: n = 15
Output: 6

Example 4:

Input: n = 24
Output: 5

Constraints:

  • 1 <= n <= 10^4

Explanation

First group numbers by sum of their digits. And then group by the length of the first groups result. Finally find the group with maximum group size.

Python Solution

class Solution:
    def countLargestGroup(self, n: int) -> int:
        results = []
        
        groups = defaultdict(list)
        
        for i in range(1, n + 1):
            
            i_str = str(i)
            sum_digits = 0
            
            for c in i_str:
                sum_digits += int(c)
                
            if sum_digits in groups:
                groups[sum_digits].append(i)
            else:
                groups[sum_digits] = [i]
            
                        
        size_groups = {}
        
        max_size = -1
        
        for key, value in groups.items():
            max_size = max(max_size, len(value))
            size_groups[len(value)] = size_groups.get(len(value), 0) + 1
            
        
        return size_groups[max_size]
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.