Description
You are 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 (most numbers).
Examples
Input:
n = 13Output:
4Explanation:
Groups by digit sum, 4 largest.
Input:
n = 24Output:
5Explanation:
Numbers 1-24 grouped by digit sum: {1}[1], {2}[2], {3}[3], {4}[4], {5}[5], {6}[6], {7}[7], {8}[8], {9}[9], {1}[10], {2}[11], {3}[12], {4}[13], {5}[14], {6}[15], {7}[16], {8}[17], {9}[18], {10}[19], {2}[20], {3}[21], {4}[22], {5}[23], {6}[24]. Groups of size 1: {10}, size 2: {1,2,3,4}, size 3: {5,6,7,8,9}. The largest group size is 3, and there are 5 groups with this size.
Input:
n = 1Output:
1Explanation:
With n = 1, there is only the number 1, which has digit sum 1. There is exactly one group containing just {1}, so the count of largest groups is 1.
Constraints
- •
1 ≤ n ≤ 10⁴