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) —

推荐阅读:
两个因数的末尾一共有几个零,积的末尾就有几个零。  四边形整理和复习思维导图  一些常见数的倍数的特征  什么是集合?  为什么要先乘除后加减  球的体积公式推导证明  生活中的分数  关于互质数的知识(五下)  乘飞机带行李的尺寸规定  位置问题的两种情况 
评论列表
添加评论