Algorithm to Count the Largest Group of Digit Sums

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