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