Digit sum of a number is the sum of all digits in the number.
Given two numbers 1 <= a < b <= 1e18, find the frequency of the most frequent digit sum for all integers in the range [a,b]. Also, find the number of times this maximum frequency is attained.
- if a=1 and b=5, then the maximum frequency is 1 and is attained 5 times.
- If a=1 and b=10, then the maximum frequency is 2 and is attained once.
I was unable to do better than iterating from a to b and updating a count array, and finally calculating the answer from this count array. Cleary this method is inadequate given the constraints. Any help is appreciated.