题目描述

给你一个整数 n。请你先求出从 1 到 n 的每个整数的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。

样例

输入：n = 13
输出：4
解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。
总共有 4 个组拥有的数字并列最多。

输入：n = 2
输出：2
解释：总共有 2 个大小为 1 的组 [1]，[2]。

输入：n = 15
输出：6

输入：n = 24
输出：5

限制

• 1 <= n <= 10^4

算法

(暴力枚举) $O(n \log n)$

1. 求出每个数字的数位和，用一个哈希表来统计每种数位和的个数，然后求出最大值有多少个。

时间复杂度

• 求每个数字的数位和的时间复杂度为 $O(n \log n)$。
• 数位和的种类数肯定低于 $O(n)$，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储哈希表。

C++ 代码

class Solution {
public:
    int countLargestGroup(int n) {
        vector<int> sum(40, 0);
        for (int i = 1; i <= n; i++) {
            int x = i, y = 0;
            while (x) {
                y += x % 10;
                x /= 10;
            }
            sum[y]++;
        }

        int ma = 0;
        for (int i = 1; i <= 36; i++)
            ma = max(ma, sum[i]);

        int ans = 0;
        for (int i = 1; i <= 36; i++)
            if (ma == sum[i])
                ans++;

        return ans;
    }
};