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: 6

Example 4
Input: n = 24
Output: 5

Constraints:
1 <= n <= 10^4

Hints:
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 
评论列表
添加评论