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 <= 104class Solution {
public int countLargestGroup(int n) {
int[] freq = new int[40]; // largest sum of digits possible is 36 (for 9999) under constraint n <= 10000
for (int i = 1; i <= n; i++) {
int key = sumOfDigits(i);
freq[key]++;
}
int maxSize = 0, count = 0;
for (int i = 1; i < 40; i++) {
if (freq[i] > maxSize) {
maxSize = freq[i];
count = 1;
} else if (freq[i] == maxSize)
count++;
}
return count;
}
private int sumOfDigits(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
}