Maximum frequency of Digit Sum in a given range

general
,
1

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.

For example,

  • 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.

2

@udayan14 please refer this link : https://www.geeksforgeeks.org/digit-dp-introduction/
and try to solve this problem first : https://www.hackerearth.com/problem/algorithm/sum-of-digits-8/description/
feel free to ask if you have any problem.