The following question came for Lucid Online Assessment:

Given a lowLimit and highLimit.
Find the maximum frequency of the same sum of digits.

Example:
lowLimit=1
highLimit=10
So the corresponding sum of digits are:
1-> 1
2->2
3->3
4->4
5->5
6->6
7->7
8->8
9->9
10->1

Thus the answer is 1. Because the frequency for sumofDigits being 1 is 2 which is the maximum in this case.

Note: The normal Brute Force approach of O(N) is giving TLE.
the range is from 1 to 10^18

Any suggestions how to solve it?