Problem

You are given an integer n.

Each number from 1 to n is grouped according to the sum of its digits.

Return the number of groups that have the largest size.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

Constraints:

  • 1 <= n <= 10^4

Solution

Method 1 - Using Hashtable

Here is the approach:

  1. Summing Digits:
    • Group numbers by their digit sums. For example, for n = 13, the values 1..13 would be grouped by sums such as 1 (1), 2 (2), 3, 12 (3+0, 1+2), etc.
    • This can be computed easily using the “digit sum” logic where we repeatedly add the digits together for each number up to n.
  2. Count Groups:
    • Use a dictionary to count how many numbers fall into each group based on their digit sums.
  3. Find Largest Group:
    • Identify the maximum group size and count how many groups achieve this size.
  4. Implementation in Python and Java:
    • Write clean and concise code for both languages following best practices.
    • Use efficient data structures to ensure the solution is optimised.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int countLargestGroup(int n) {
        HashMap<Integer, Integer> count = new HashMap<>();

        // Count group sizes by digit sum
        for (int i = 1; i <= n; i++) {
            int s = digitSum(i);
            count.put(s, count.getOrDefault(s, 0) + 1);
        }

        // Find the largest group size
        int maxSize = 0;
        for (int size : count.values()) {
            maxSize = Math.max(maxSize, size);
        }

        // Count groups of the largest size
        int ans = 0;
        for (int size : count.values()) {
            if (size == maxSize) {
                ans++;
            }
        }

        return ans;
    }

    // Helper function to calculate sum of digits
    private int digitSum(int x) {
        int total = 0;
        while (x > 0) {
            total += x % 10;
            x /= 10;
        }
        return total;
    }
}
 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:
    def countLargestGroup(self, n: int) -> int:
        count: defaultdict[int, int] = defaultdict(int)
        
        # Helper to calculate digit sum
        def digit_sum(x: int) -> int:
            total = 0
            while x > 0:
                total += x % 10
                x //= 10
            return total
        
        # Count group sizes by digit sum
        for i in range(1, n + 1):
            s = digit_sum(i)
            count[s] += 1
        
        # Find the largest group size
        max_size = max(count.values())
        
        # Count groups of the largest size
        ans = sum(1 for group in count.values() if group == max_size)
        
        return ans

Complexity

  • ⏰ Time complexity:  O(n * d) where d is the number of digits in a number (logarithmic in the base of 10).
    • Calculating the digit sum takes O(d), and we do this for all numbers from 1 to n.
  • 🧺 Space complexity: O(n) for storing counts in a dictionary or map.