1399. Count Largest Group

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits. 

Return how many groups 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.
Example 3:

Input: n = 15
Output: 6
Example 4:

Input: n = 24
Output: 5
 

Constraints:

1 <= n <= 10^4

这题主要先要求出符合条件的最大组的尺寸，然后计算有多少个这个尺寸的。我这里写了两个算法，就空间复杂度有点差异，其余大同小异。

class CountLargestGroup : public Solution {
public:
    void Exec() {
        auto res = countLargestGroup(24);
    }
    int countLargestGroup1(int n) {
        unordered_map<int, int> counters;
        int maxCount = -1;
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            int num = i;
            while (num != 0) {
                sum += num % 10;
                num /= 10;
            }
            
            auto it = counters.find(sum);
            if (it == counters.end()) {
                it = counters.insert(std::make_pair(sum, 1)).first;
            } else {
                it->second++;
            }
            if (it->second > maxCount) {
                maxCount = it->second;
            }
        }
        int res = 0;
        for (auto &pa : counters) {
            if (pa.second == maxCount) {
                ++res;
            }
        }
        return res;
    }
    int countLargestGroup(int n) {
        vector<int> digitSums(n, 0);
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            int num = i;
            while (num != 0) {
                sum += num % 10;
                num /= 10;
            }
            digitSums[i - 1] = sum;
        }
        std::sort(digitSums.begin(), digitSums.end());
        
        unordered_map<int, int> counters;
        int maxCount = -1, *prev = nullptr, curCount = 0;
        for (int i = 0; i < digitSums.size(); i++) {
            if (prev == nullptr || *prev == digitSums[i]) {
                curCount++;
            } else {
                // Add counters
                auto it = counters.find(curCount);
                if (it == counters.end()) {
                    counters.insert(std::make_pair(curCount, 1));
                } else {
                    it->second++;
                }
                if (curCount > maxCount) {
                    maxCount = curCount;
                }
                curCount = 1;
            }
            prev = &digitSums[i];
        }
        // Handle last element
        auto it = counters.find(curCount);
        if (it == counters.end()) {
            counters.insert(std::make_pair(curCount, 1));
        } else {
            it->second++;
        }
        if (curCount > maxCount) {
            maxCount = curCount;
        }

        return counters[maxCount];
    }
};