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
Solution: HashTable
Time complexity: O(nlogn)
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int countLargestGroup(int n) { vector<int> c(37); // max sum is 9+9+9+9 = 36 for (int i = 1; i <= n; ++i) { int x = i; int sum = 0; while (x) { sum += x % 10; x /= 10; } ++c[sum]; } return count(begin(c), end(c), *max_element(begin(c), end(c))); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment