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.

$\endgroup$
6
  • $\begingroup$ By "iterate", you mean you actually go about and calculate the weight for each number? $\endgroup$
    – Arturo Magidin
    Jun 24, 2011 at 4:17
  • $\begingroup$ 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? $\endgroup$
    – Emre
    Jun 24, 2011 at 4:21
  • $\begingroup$ @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. $\endgroup$
    – Geuis
    Jun 24, 2011 at 4:24
  • $\begingroup$ @Emre I believe in this context, its an exact figure that's expected for the total count of heavy numbers. $\endgroup$
    – Geuis
    Jun 24, 2011 at 4:26
  • $\begingroup$ 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. $\endgroup$
    – Ross Millikan
    Jun 24, 2011 at 5:06

2 Answers 2

Reset to default
7
$\begingroup$

If you want to calculate the answer exactly, one way to go is using generating functions (which is the same as dynamic programming).

Let's restrict ourselves first to some particular length, say $5$. We are going to calculate how many numbers with exactly $5$ digits have digits that sum to more than $35$.

The generating function for the sum of digits is $$ (x+\cdots+x^9)(1+\cdots+x^9)^4. $$ You want to sum the coefficients of $x^k$ for all $k \geq 36$.

As mentioned above, this approach reduces to a dynamic programming algorithm. The algorithm computes inductively how many number of length exactly $l \leq 5$ have a certain digit sum. I'll leave you the details.

In case your range is more complicated, you break it up. First, we can handle something like "all numbers of length 5 starting with 1,2,3" by adjusting the first factor. Second, you can break up an arbitrary range $[0,n]$ into ranges of that form (plus extra "constant" digits that affect only the choice of the threshold). Finally, use $[l,h] = [0,h] - [0,l-1]$ to handle an arbitrary range.

If you only want to estimate the number, the way to go is the Central Limit Theorem, or rather Large Deviation Theory. The sum of digits of an $n$-digit number is approximated by a normal variable - but not far from the mean, which is what you're looking for. Still, there are estimates on the error of the normal approximation which can be useful. Methods from Large Deviation Theory may give more accurate results.

$\endgroup$
2
  • $\begingroup$ Thanks Yuval. I know this is the correct answer, but I still can only parse small parts of it. That's my fault, no one else's. I need to read up more on dynamic programming to be able to fully digest your solution. $\endgroup$
    – Geuis
    Jun 24, 2011 at 5:41
  • $\begingroup$ @Geuis I'm having the same issue. I can't quite wrap my head around this solution. If I do end up figuring it out, I'll try to edit the answer to show a few more steps. If anyone else beats me to it that would be fine too! $\endgroup$
    – sgryzko
    Oct 3, 2015 at 4:18
3
$\begingroup$

I have investigated this issue a bit more depth and implemented two solutions. Please refer to

http://cpluspluslearning-petert.blogspot.co.uk/2014/07/dynamic-programming-heavy-numbers.html

http://cpluspluslearning-petert.blogspot.co.uk/2014/07/dynamic-programming-heavy-numbers-part.html

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .