Optimal and efficient solution for the heavy number calculation?

Question

I need to find the number of heavy integers between two integers A and B, where A <= B at all times.

An integer is considered heavy whenever the average of it's digit is larger than 7.

For example: 9878 is considered heavy, because (9 + 8 + 7 + 8)/4 = 8 , while 1111 is not, since (1 + 1 + 1 + 1)/4 = 1.

I have the solution below, but it's absolutely terrible and it times out when run with large inputs. What can I do to make it more efficient?

int countHeavy(int A, int B) {
    int countHeavy = 0;

    while(A <= B){
        if(averageOfDigits(A) > 7){
            countHeavy++;
        }
        A++;
    }

    return countHeavy;
}
 
float averageOfDigits(int a) {
    float result = 0;
    int count = 0;

    while (a > 0) {
        result += (a % 10);
        count++;
        a = a / 10;
    }

    return result / count;
}

Answer 1

Counting the numbers with a look-up table

You can generate a table that stores how many integers with d digits have a sum of their digits that is greater than a number x. Then, you can quickly look up how many heavy numbers there are in any range of 10, 100, 1000 ... integers. These tables hold only 9×d values, so they take up very little space and can be quickly generated.

Then, to check a range A-B where B has d digits, you build the tables for 1 to d-1 digits, and then you split the range A-B into chunks of 10, 100, 1000 ... and look up the values in the tables, e.g. for the range A = 782, B = 4321:

   RANGE      DIGITS  TARGET     LOOKUP      VALUE

 782 -  789     78x    > 6    table[1][ 6]     3    <- incomplete range: 2-9
 790 -  799     79x    > 5    table[1][ 5]     4
 800 -  899     8xx    >13    table[2][13]    15
 900 -  999     9xx    >12    table[2][12]    21
1000 - 1999    1xxx    >27    table[3][27]     0
2000 - 2999    2xxx    >26    table[3][26]     1
3000 - 3999    3xxx    >25    table[3][25]     4
4000 - 4099    40xx    >24    impossible       0
4100 - 4199    41xx    >23    impossible       0
4200 - 4299    42xx    >22    impossible       0
4300 - 4309    430x    >21    impossible       0
4310 - 4319    431x    >20    impossible       0
4320 - 4321    432x    >19    impossible       0    <- incomplete range: 0-1
                                              --
                                              48

If the first and last range are incomplete (not *0 - *9), check the starting value or the end value against the target. (In the example, 2 is not greater than 6, so all 3 heavy numbers are included in the range.)

Generating the look-up table

For 1-digit decimal integers, the number of integers n that is greater than value x is:

x:  0  1  2  3  4  5  6  7  8  9
n:  9  8  7  6  5  4  3  2  1  0

As you can see, this is easily calculated by taking n = 9-x.

For 2-digit decimal integers, the number of integers n whose sum of digits is greater than value x is:

x:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
n:  99 97 94 90 85 79 72 64 55 45 36 28 21 15 10  6  3  1  0

For 3-digit decimal integers, the number of integers n whose sum of digits is greater than value x is:

x:   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27
n: 999 996 990 980 965 944 916 880 835 780 717 648 575 500 425 352 283 220 165 120  84  56  35  20  10   4   1   0

Each of these sequences can be generated from the previous one: start with value 10^d and then subtract from this value the previous sequence in reverse (skipping the first zero). E.g. to generate the sequence for 3 digits from the sequence for 2 digits, start with 10³ = 1000, and then:

 0. 1000 -   1      = 999
 1.  999 -   3      = 996
 2.  996 -   6      = 990
 3.  990 -  10      = 980
 4.  980 -  15      = 965
 5.  965 -  21      = 944
 6.  944 -  28      = 916
 7.  916 -  36      = 880
 8.  880 -  45      = 835
 9.  835 -  55      = 780
10.  780 -  64 +  1 = 717  <- after 10 steps, start adding the previous sequence again
11.  717 -  72 +  3 = 648
12.  648 -  79 +  6 = 575
13.  575 -  85 + 10 = 500
14.  500 -  90 + 15 = 425
15.  425 -  94 + 21 = 352
16.  352 -  97 + 28 = 283
17.  283 -  99 + 36 = 220
18.  220 - 100 + 45 = 165  <- at the end of the sequence, keep subtracting 10^(d-1)
19.  165 - 100 + 55 = 120
20.  120 - 100 + 64 =  84
21.   84 - 100 + 72 =  56
22.   56 - 100 + 79 =  35
23.   35 - 100 + 85 =  20
24.   20 - 100 + 90 =  10
25.   10 - 100 + 94 =   4
26.    4 - 100 + 97 =   1
27.    1 - 100 + 99 =   0

By the way, you can use the same tables if "heavy" numbers are defined with a value other than 7.

---

Code example

Below is a Javascript code snippet (I don't speak Java) that demonstrates the method. It is very much unoptimised, but it does the 0→100,000,000 example in less than 0.07ms. It also works for weights other than 7. Translated to Java, it should easily beat any algorithm that actually runs through the numbers and checks their weight.

function countHeavy(A, B, weight) {
    var a = decimalDigits(A), b = decimalDigits(B);        // create arrays
    while (a.length < b.length) a.push(0);                 // add leading zeros
    var digits = b.length, table = weightTable();          // create table
    var count = 0, diff = B - A + 1, d = 0;                // calculate range
    for (var i = digits - 1; i >= 0; i--) if (a[i]) d = i; // lowest non-0 digit
    while (diff) {                                         // increment a until a=b
        while (a[d] == 10) {                               // move to higher digit
            a[d++] = 0;
            ++a[d];                                        // carry 1
        }
        var step = Math.pow(10, d);                        // value of digit d
        if (step <= diff) {
            diff -= step;
            count += increment(d);                         // increment digit d
        }
        else --d;                                          // move to lower digit
    }
    return count;

    function weightTable() {                               // see above for details
        var t = [[],[9,8,7,6,5,4,3,2,1,0]];
        for (var i = 2; i < digits; i++) {
            var total = Math.pow(10, i), final = total / 10;
            t[i] = [];
            for (var j = 9 * i; total > 0; --j) {
                if (j > 9) total -= t[i - 1][j - 10]; else total -= final;
                if (j < 9 * (i - 1)) total += t[i - 1][j];
                t[i].push(total);
            }
        }
        return t;
    }
    function increment(d) {
        var sum = 0, size = digits;
        for (var i = digits - 1; i >= d; i--) {
            if (a[i] == 0 && i == size - 1) size = i;      // count used digits
            sum += a[i];                                   // sum of digits
        }
        ++a[d];
        var target = weight * size - sum;
        if (d == 0) return (target < 0) ? 1 : 0;           // if d is lowest digit
        if (target < 0) return table[d][0] + 1;            // whole range is heavy
        return (target > 9 * d) ? 0 : table[d][target];    // use look-up table
    }
    function decimalDigits(n) {
        var array = [];
        do {array.push(n % 10);
            n = Math.floor(n / 10);
        } while (n);
        return array;
    }
}
document.write("0 &rarr; 100,000,000 = " + countHeavy(0, 100000000, 7) + "<br>");
document.write("782 &rarr; 4321 = " + countHeavy(782, 4321, 7) + "<br>");
document.write("782 &rarr; 4321 = " + countHeavy(782, 4321, 5) + " (weight: 5)");