Count how many integer groups have the largest size when numbers from $1n$ are grouped by the sum of their digits.
Problem
Given a positive integer , consider the integers from $1n$ inclusive. Group each integer by the sum of its decimal digits.
For example, if :
- $1, 10 belong to the group with digit sum \1$
- $2, 11 belong to the group with digit sum \2$
- $3, 12 belong to the group with digit sum \3$
- and so on
Your task is to determine how many groups have the maximum number of elements.
In other words, among all digit-sum groups formed by numbers from $1n$, find the largest group size and return the number of groups whose size equals that maximum.
Input Format
- A single integer .
Output Format
- Return the number of digit-sum groups that have the largest size.
Constraints
Example 1
Input
n = 13
Output
4
Explanation
The groups with digit sums 1, 2, 3, and 4 each contain 2 numbers: {1,10}, {2,11}, {3,12}, and {4,13}. So there are 4 largest groups.
Example 2
Input
n = 2
Output
2
Explanation
The groups are {1} and {2}. Both have size 1, so the answer is 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.