Problem Statement in English

You’re given an integer n. The digit sum of an integer is the sum of all its digits. For example, the digit sum of 1328 is 1 + 3 + 2 + 8 = 14.

You have to count the number of integers in the range [1, n] that have the same digit sum as n, and return the group with the largest size.

Approach

This problem can be solved using a dictionary to keep track of the digit sums and their counts.

Solution in Python


class Solution:
    def countLargestGroup(self, n: int) -> int:
        hm = defaultdict(int)
        largestGroupSize = 0
        for i in range(1, n+1):
            s = sum(map(int, str(i)))

            hm[s] += 1
            if hm[s] > largestGroupSize:
                largestGroupSize = hm[s]

        res = 0
        for v in hm.values():
            if v == largestGroupSize:
                res += 1

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through all numbers from 1 to n, the time complexity is linear with respect to n.

  • Space: $O(n)$
    Since we are using a dictionary to store the digit sums and their counts, the space complexity is also linear with respect to n.

And we are done.