Difficulty: Easy | Acceptance: 74.70% | Paid: No Topics: Hash Table, Math, Counting
You are given an integer n.
Each number from 1 to n inclusive is grouped according to the sum of its digits.
Return the number of groups that have the largest size.
- Examples
- Constraints
- Hash Map Approach
- Array-based Counting
- Precompute Digit Sums
Examples
Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.
Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.
Constraints
1 <= n <= 10^4
Hash Map Approach
Intuition Use a hash map to count how many numbers share each digit sum, then find the maximum count and count how many groups achieve it.
Steps
- Iterate from 1 to n, calculating digit sum for each number
- Store counts in a hash map keyed by digit sum
- Find the maximum group size
- Count how many groups have this maximum size
python
from collections import defaultdict
class Solution:
def countLargestGroup(self, n: int) -> int:
groups = defaultdict(int)
for i in range(1, n + 1):
sum_digits = 0
num = i
while num:
sum_digits += num % 10
num //= 10
groups[sum_digits] += 1
max_size = max(groups.values())
return sum(1 for v in groups.values() if v == max_size)
Complexity
- Time: O(n × log₁₀n) for calculating digit sums
- Space: O(n) for storing group counts
- Notes: Simple and intuitive, uses extra space for hash map overhead
Array-based Counting
Intuition Since the maximum digit sum for n ≤ 10⁴ is 36 (for 9999), use a fixed-size array instead of a hash map for better performance.
Steps
- Create an array of size 37 to store counts for each possible digit sum
- Iterate through 1 to n, calculating digit sum and incrementing the corresponding array index
- Find the maximum value in the array
- Count how many indices contain this maximum value
python
class Solution:
def countLargestGroup(self, n: int) -> int:
def digit_sum(num):
s = 0
while num:
s += num % 10
num //= 10
return s
groups = [0] * 37
for i in range(1, n + 1):
groups[digit_sum(i)] += 1
max_size = max(groups)
return groups.count(max_size)
Complexity
- Time: O(n × log₁₀n) for calculating digit sums
- Space: O(1) since array size is fixed at 37
- Notes: More efficient than hash map due to direct array access and no overhead
Precompute Digit Sums
Intuition Use dynamic programming to precompute all digit sums, avoiding repeated digit extraction for each number.
Steps
- Create an array where digit_sums[i] = digit_sums[i // 10] + i % 10
- Fill the array from 1 to n using the recurrence relation
- Count groups using the precomputed digit sums
- Find and count the maximum group size
python
class Solution:
def countLargestGroup(self, n: int) -> int:
digit_sums = [0] * (n + 1)
for i in range(1, n + 1):
digit_sums[i] = digit_sums[i // 10] + i % 10
groups = [0] * 37
for i in range(1, n + 1):
groups[digit_sums[i]] += 1
max_size = max(groups)
return groups.count(max_size)
Complexity
- Time: O(n) for single pass precomputation
- Space: O(n) for storing precomputed digit sums
- Notes: Faster digit sum calculation at the cost of O(n) extra space