Description#
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:
Solutions#
Solution 1: Hash Table or Array#
We note that the number does not exceed $10^4$, so the sum of the digits also does not exceed $9 \times 4 = 36$. Therefore, we can use a hash table or an array of length $40$, denoted as $cnt$, to count the number of each sum of digits, and use a variable $mx$ to represent the maximum count of the sum of digits.
We enumerate each number in $[1,..n]$, calculate its sum of digits $s$, then increment $cnt[s]$ by $1$. If $mx < cnt[s]$, we update $mx = cnt[s]$ and set $ans$ to $1$. If $mx = cnt[s]$, we increment $ans$ by $1$.
Finally, we return $ans$.
The time complexity is $O(n \times \log M)$, and the space complexity is $O(\log M)$. Where $n$ is the given number, and $M$ is the range of $n$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def countLargestGroup(self, n: int) -> int:
cnt = Counter()
ans = mx = 0
for i in range(1, n + 1):
s = 0
while i:
s += i % 10
i //= 10
cnt[s] += 1
if mx < cnt[s]:
mx = cnt[s]
ans = 1
elif mx == cnt[s]:
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int countLargestGroup(int n) {
int[] cnt = new int[40];
int ans = 0, mx = 0;
for (int i = 1; i <= n; ++i) {
int s = 0;
for (int x = i; x > 0; x /= 10) {
s += x % 10;
}
++cnt[s];
if (mx < cnt[s]) {
mx = cnt[s];
ans = 1;
} else if (mx == cnt[s]) {
++ans;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int countLargestGroup(int n) {
int cnt[40]{};
int ans = 0, mx = 0;
for (int i = 1; i <= n; ++i) {
int s = 0;
for (int x = i; x; x /= 10) {
s += x % 10;
}
++cnt[s];
if (mx < cnt[s]) {
mx = cnt[s];
ans = 1;
} else if (mx == cnt[s]) {
++ans;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func countLargestGroup(n int) (ans int) {
cnt := [40]int{}
mx := 0
for i := 1; i <= n; i++ {
s := 0
for x := i; x > 0; x /= 10 {
s += x % 10
}
cnt[s]++
if mx < cnt[s] {
mx = cnt[s]
ans = 1
} else if mx == cnt[s] {
ans++
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function countLargestGroup(n: number): number {
const cnt: number[] = new Array(40).fill(0);
let mx = 0;
let ans = 0;
for (let i = 1; i <= n; ++i) {
let s = 0;
for (let x = i; x; x = Math.floor(x / 10)) {
s += x % 10;
}
++cnt[s];
if (mx < cnt[s]) {
mx = cnt[s];
ans = 1;
} else if (mx === cnt[s]) {
++ans;
}
}
return ans;
}
|
