9
$\begingroup$

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.

Example:

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.

  • 0
    By "iterate", you mean you actually go about and calculate the weight for each number?2011-06-24
  • 0
    Do they want the exact number or is an approximation enough? Maybe it would help to partition the range by the number of digits, and find the number of "heavies" in each one. The question then becomes: how many heavy numbers are there with $k$ digits?2011-06-24
  • 0
    @Arturo yeah, basically looping over the entire range. 1000, 1001, 1002, etc. I'm at a loss as to what the more efficient way is.2011-06-24
  • 0
    @Emre I believe in this context, its an exact figure that's expected for the total count of heavy numbers.2011-06-24
  • 0
    A Google search doesn't show a definition of "heavy numbers". So you (or the interviewer) should give a clear definition. The *second* challenge is to find a (moderately) good algorithm to find them.2011-06-24
  • 0
    Oh, I agree 100%. Hence part of my initial question is what this type of thing is *actually* called because my searches for explanatory information resulted in very little.2011-06-24

2 Answers 2