Algorithm to Count the Largest Group of Digit Sums
- 时间:2020-10-11 15:48:46
- 分类:网络文摘
- 阅读:83 次
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: 6Example 4
Input: n = 24
Output: 5Constraints:
1 <= n <= 10^4Hints:
Count the digit sum for each integer in the range and find out the largest groups.
Algorithm to Count the Largest Group
As the input range is up to 10^4 – which gives the maximum groups of 36 as the 9+9+9+9 digit sum of 9999 is 36.
Then, we can just compute the sum of digits for each number in the range, increment the corresponding counter, and return the maximum group.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: int countLargestGroup(int n) { int count[37] = {}; int curMax = 0; int ans = 0; for (int i = 1; i <= n; ++ i) { int j = i; int r = 0; while (j > 0) { r += (j % 10); j /= 10; } count[r] ++; if (count[r] > curMax) { curMax = count[r]; ans = 1; } else if (count[r] == curMax) { ans ++; } } return ans; } }; |
class Solution { public: int countLargestGroup(int n) { int count[37] = {}; int curMax = 0; int ans = 0; for (int i = 1; i <= n; ++ i) { int j = i; int r = 0; while (j > 0) { r += (j % 10); j /= 10; } count[r] ++; if (count[r] > curMax) { curMax = count[r]; ans = 1; } else if (count[r] == curMax) { ans ++; } } return ans; } };
We don’t have to iterative twice. By remembering/updating the current maximum counter, we can just increment the answer along the way.
The complexity is O(1) constant time as we only need to process each numbers in the range which is 9999 numbers maximum. The space requirement is also constant.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Examining the Physical and Mental Health of Writers and Bloggers How will Blogging Change after the Pandemic? Digital Relationships: 5 Tips For Building A Better Veterinary B The 2020 Pandemic Further Boosts Earnings and Influence of Blogg What to Do When Your Blog Gets Too Big for You Alone Minimum Numbers of Function Calls to Make Target Array Harddrives will fail – it is just a matter of when Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve DFS and BFS Algorithm to Find Numbers With Same Consecutive Diff How to Remove Items/Entries with Specific Values from Map/HashMa
- 评论列表
-
- 添加评论