Count Largest Group — LeetCode 1399 Python Solution

The problem

You are given an integer n. We need to group the numbers from 1 to n according to the sum of its digits.

Example

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:

Python solution

class Solution:
    def countLargestGroup(self, n: int) -> int:
        cnt = Counter()
        ans = mx = 0
        for i in range(1, n + 1):
            s = 0
            while i:
                s += i % 10
                i //= 10
            cnt[s] += 1
            if mx < cnt[s]:
                mx = cnt[s]
                ans = 1
            elif mx == cnt[s]:
                ans += 1
        return ans

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1399. Count Largest Group is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems