Maximum frequency of Digit Sum in a given range

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 Likes

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

1 Like

For anyone looking for the answer in 2022, one possible solution is to solve the hackerearth problem for s = 1 to 9*17 (i.e. max possible digit sum) and store the results in an array.

Use this array to answer this problem, i.e. find max value in the array and the frequency of said max value.

The solution to the hacker earth problem is very similar to the basic sum problem from geeksforgeeks. Build a dp, but instead of storing a sum, store a target digit sum (which will be decremented). Have appropriate boundary conditions. The same dp table can be reused for different values of s.

@sna902055 correct me if wrong :grin: