Groups of numbers
Group the numbers 1 to n by their digit sum and find the biggest groups. About 9 minutes.
A key you work out
The key doesn't have to be the item itself. You can work it out from the item. Here, group every number from 1 to n by the sum of its digits: 13 has digit sum 1 + 3 = 4, so it joins 4 in group 4.
A map from each digit sum to how many numbers are in that group keeps track of every group's size as you go.
1 to 9 are one digit each, so each is its own digit sum. Nine groups of 1.
Then look at the groups
Once every number has found its group, look at the sizes. Find the biggest size, then count how many groups reach it.
Notice the answer counts groups, not numbers. For n = 13, four groups (digit sums 1, 2, 3 and 4) each have 2 numbers, and that's the biggest size, so the answer is 4.
size = {}
for x in range(1, n + 1):
key = sum(int(d) for d in str(x))
size[key] = size.get(key, 0) + 1
biggest = max(size.values())
return list(size.values()).count(biggest)In which digit-sum group is 29?
- A11
- B2
- C29
Show the answer
11. 2 + 9 = 11.
Biggest digit-sum groups
Put each number from 1 to n into a group by the sum of its digits. Return how many groups have the largest size.
n = 13 → 4
1 ≤ n ≤ 1,000,000