I had an interview question a couple days ago involving the calculation of the amount of heavy numbers between in a given range. I came up with a basic solution, which was to iterate over the entire range and test for the heaviness of each number. I realized right away that its a terribly inefficient method of solving the problem. In the interest of educating myself I have been tackling the problem today to try and learn more about this type of problem. Its tough for me, because I don't have a super strong mathematics background but I'm trying to learn.
Basically, the problem goes like this:
Take any 2 numbers from 0 to 200,000,000. In that range, calculate the number of "heavy numbers". This is calculated by adding together all of the component digits and then dividing by the number of components. If the average is greater than 7, the number is considered heavy.
1234: 1+2+3+4/4 = 2.5 (not heavy) 8996: 8+9+9+6/4 = 8 (heavy)
So given the range 1002 - 12089, my naive approach is to iterate over each number between and calculate its weight. This approach quickly falls apart when dealing with very large number ranges.
I've done quite a bit of searching via Google and Bing and beyond a couple of posts where people have copy/pasted verbatim the question, I find almost no information about this kind of problem. I suspect that this type of problem is called something other than "heavy numbers" but I'm at a loss as to what that the terminology is.
Here is a link to one such discussion: http://groups.google.com/group/algogeeks/browse_thread/thread/a1b824107afe3801
I'm hoping that someone who is familiar with type of scenario can explain alternative ways to solve the problem in a simple manner, and that I might ask follow up questions until I understand.
Thanks for reading.