LeetCode 1399. Count the maximum number of groups

1399. Count the number of the largest groups

Give you an integer n . Please find out from 1 To n Each integer of 10 Hexadecimal represents the sum of digits under （ Add the numbers on each digit ）, Then put the digits and equal numbers in the same group .

Please count the number of numbers in each group , And return the number of groups with the largest number of numbers .

Example 1：

 Input ：n = 13
 Output ：4
 explain ： All in all  9  A set of , take  1  To  13  After summing by digits, these groups are ：
[1,10],[2,11],[3,12],[4,13],[5],[6],[7],[8],[9]. All in all  4  Groups have the most numbers in parallel .

Example 2：

 Input ：n = 2
 Output ：2
 explain ： All in all  2  Size is  1  Group  [1],[2].

Example 3：

 Input ：n = 15
 Output ：6

Example 4：

 Input ：n = 24
 Output ：5

Tips ：

• 1 <= n <= 10^4

Two 、 Method 1

Hash storage statistics is enough

class Solution {
    
    public int countLargestGroup(int n) {
    
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int maxValue = 0;
        for (int i = 1; i <= n; ++i) {
    
            int key = 0, i0 = i;
            while (i0 != 0) {
    
                key += i0 % 10;
                i0 /= 10;
            }
            hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
            maxValue = Math.max(maxValue, hashMap.get(key));
        }
        int count = 0;
        for (Map.Entry<Integer, Integer> kvpair : hashMap.entrySet()) {
    
            if (kvpair.getValue() == maxValue) {
    
                ++count;
            }
        }
        return count;
    }
}

Complexity analysis

• Time complexity ： logarithm x The time to sum digits is O(log 10x)=O(logx), Therefore, the total time cost is O(nlogn), The time cost of selecting the largest element and traversing the hash table is O(n), Therefore, the time complexity gradually O(nlogn)+O(n)=O(nlogn).

• Spatial complexity ： Use hash table as secondary space ,n The number of digits is O(log 10 n)=O(logn), Every digit is [0,9] Between , Therefore, the maximum number of keys contained in the hash table is O(10logn)=O(logn), The asymptotic space complexity is O(logn).