You are given an integer n.
Each number from 1 to n is grouped according to the sum of its digits.
Return the number of groups that 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.
Constraints:
1 <= n <= 104
Approach 01:
-
C++
-
Python
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int countLargestGroup(int n) {
vector<int> groupSizes(36 + 1, 0);
for (int number = 1; number <= n; ++number) {
int sum = calculateDigitSum(number);
++groupSizes[sum];
}
int maxSize = *max_element(groupSizes.begin(), groupSizes.end());
return count(groupSizes.begin(), groupSizes.end(), maxSize);
}
private:
int calculateDigitSum(int num) {
int digitSum = 0;
while (num > 0) {
digitSum += num % 10;
num /= 10;
}
return digitSum;
}
};
Time Complexity:
- Digit Sum Calculation:
For each number from 1 to \(n\), we compute its digit sum in \(O(\log_{10} n)\) time. Over all \(n\) numbers, this is \(O(n \log n)\).
- Finding Maximum and Counting:
Scanning the fixed-size vector of length 37 takes \(O(1)\) time.
- Total Time Complexity:
\(O(n \log n)\).
Space Complexity:
- Group Sizes Array:
Uses a fixed-size array of length 37 → \(O(1)\).
- Auxiliary Variables:
Only loop counters and a few integers → \(O(1)\).
- Total Space Complexity:
\(O(1)\).
from typing import List
from collections import Counter
class Solution:
def countLargestGroup(self, n: int) -> int:
def calculate_digit_sum(num: int) -> int:
s = 0
while num:
s += num % 10
num //= 10
return s
groupSizes = Counter(calculate_digit_sum(i) for i in range(1, n + 1))
maxSize = max(groupSizes.values())
return sum(1 for size in groupSizes.values() if size == maxSize)
Time Complexity:
- Digit Sum Calculation:
For each integer from 1 to n, we compute its digit sum in \( O(\log_{10} n) \) time. Over n numbers, this is \( O(n \log n) \).
- Counting Groups:
Updating the Counter for n values is \( O(n) \).
- Finding Maximum and Counting:
Scanning the Counter’s values takes \( O(k) \), where k ≤ n is the number of distinct digit sums.
- Total Time Complexity:
\( O(n \log n) \).
Space Complexity:
- Counter Storage:
We store up to k ≤ n entries for distinct digit sums → \( O(n) \).
- Auxiliary Variables:
Constant additional space for counters and loop variables → \( O(1) \).
- Total Space Complexity:
\( O(n) \).