重量级数字计算的最佳高效解决方案是什么？

Question

我需要找到两个整数和之间的重整数数量，其中始终成立。

重整数是指其数字平均值大于<7>时的整数。

例如：<9878>被认为是重量级的，因为< (9 + 8 + 7 + 8)/4 = 8 >，而<1111>则不是，因为< (1 + 1 + 1 + 1)/4 = 1 >。

我有以下解决方案，但它非常糟糕，并且在大输入时超时。我该怎么做才能使其更有效？

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;
}

- theJuls

---

在 averageOfDigits 函数中，我会将结果设为 int 类型，然后简单地使用 return (float)result / count;。这样可以一直使用整数运算，直到函数返回。可能不是很大的优化，但仍然有用... - Rudy Velthuis

如果A >= B始终成立，那么A应该递减，并且条件应该是while (A >= B)。 - Rudy Velthuis

可以使用动态规划或记忆化，在log(A)时间内完成。如果循环遍历第一个数字的所有可能性，则可以计算剩余数字的可能性。你所追求的平均数将是一个参数而不是一个固定的7。但编码过程中需要注意处理前导0和<=A的条件，比较麻烦。也许可以先从更简单的“恰好有k位数字的重数”开始尝试。 - Paul Hankin

啊，好的。我希望你已经完全复制了你的代码，而不是在这个网页的编辑器中输入它？打字错误可能会使代码看起来有错，但实际上原始源代码并没有问题。这就是为什么我们喜欢看到真正的源代码，而不是某种模拟。 - Rudy Velthuis

A/B的范围是多少？ - vish4071

Answer 1

使用查找表计算数字数量

你可以生成一个表格，存储有多少个d位数的整数其各位数字之和大于一个数字x。然后，你可以快速查找任意10、100、1000……个整数范围内有多少重量级数字。这些表格仅包含9×d个值，因此它们占用的空间非常小，可以快速生成。

然后，要检查B具有d位数字的范围A-B，你需要构建1到d-1位数的表格，然后将范围A-B分成10、100、1000……的块，并在表格中查找值，例如对于范围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

如果第一个和最后一个范围不完整（不是*0 - *9），请检查起始值或结束值是否大于目标值。（在本例中，2不大于6，因此所有3个重数字都包括在范围内。）

生成查找表

对于1位小数整数，大于值x的整数n的数量为：

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

如您所见，这可以通过取n = 9-x来轻松计算。

对于两位十进制整数，其数位之和大于值x的整数数量为：n。

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

对于三位小数整数，其各个数字之和大于值x的整数n的数量为：

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

这些序列中的每一个都可以从前一个生成：从值10^d开始，然后从该值中逆向减去前一个序列（跳过第一个零）。例如，要从2位数序列生成3位数序列，请从10³=1000开始，然后：

 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

顺便提一下，如果“重”数字定义的值不是7，您仍然可以使用相同的表格。

---

代码示例 以下是一个Javascript代码片段（我不会说Java），演示了该方法。它并不是非常优化，但它在不到0.07毫秒的时间内完成了0→100,000,000的示例。它也适用于除7以外的权重。翻译成Java后，它应该轻松击败任何实际运行数字并检查它们的权重的算法。

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)");

- m69 ''snarky and unwelcoming''

Answer 2

我非常喜欢@m69的帖子，所以我写了一个受其启发的实现。表格的创建并不那么优雅，但是却很有效。对于n+1位数的整数，我会从n位数中最多取10个值进行求和，其中每个数字0-9都会有一个值。

我使用这种简化方法来避免任意范围的计算：

countHeavy(A, B) = countHeavy(0, B) - countHeavy(0, A-1)

结果通过两个循环计算得出。一个用于小于给定数的数字，另一个用于剩下的数字。我无法轻松地将它们合并。getResult只是查找table并进行范围检查，代码的其余部分应该很明显。

public class HeavyNumbers {
    private static int maxDigits = String.valueOf(Long.MAX_VALUE).length();
    private int[][] table = null;

    public HeavyNumbers(){
        table = new int[maxDigits + 1][];
        table[0] = new int[]{1};

        for (int s = 1; s < maxDigits + 1; ++s) {
            table[s] = new int[s * 9 + 1];
            for (int k = 0; k < table[s].length; ++k) {
                for (int d = 0; d < 10; ++d) {
                    if (table[s - 1].length > k - d) {
                        table[s][k] += table[s - 1][Math.max(0, k - d)];
                    }
                }
            }
        }
    }

    private int[] getNumberAsArray(long number) {
        int[] tmp = new int[maxDigits];
        int cnt = 0;

        while (number != 0) {
            int remainder = (int) (number % 10);
            tmp[cnt++] = remainder;
            number = number / 10;
        }

        int[] ret = new int[cnt];
        for (int i = 0; i < cnt; ++i) {
            ret[i] = tmp[i];
        }
        return ret;
    }

    private int getResult(int[] sum, int digits, int fixDigitSum, int heavyThreshold) {
        int target = heavyThreshold * digits - fixDigitSum + 1;
        if (target < sum.length) {
            return sum[Math.max(0, target)];
        }
        return 0;
    }

    public int getHeavyNumbersCount(long toNumberIncl, int heavyThreshold) {
        if (toNumberIncl <= 0) return 0;

        int[] numberAsArray = getNumberAsArray(toNumberIncl);

        int res = 0;

        for (int i = 0; i < numberAsArray.length - 1; ++i) {
            for (int d = 1; d < 10; ++d) {
                res += getResult(table[i], i + 1, d, heavyThreshold);
            }
        }

        int fixDigitSum = 0;
        int fromDigit = 1;
        for (int i = numberAsArray.length - 1; i >= 0; --i) {
            int toDigit = numberAsArray[i];
            if (i == 0) {
                toDigit++;
            }
            for (int d = fromDigit; d < toDigit; ++d) {
                res += getResult(table[i], numberAsArray.length, fixDigitSum + d, heavyThreshold);
            }

            fixDigitSum += numberAsArray[i];
            fromDigit = 0;
        }

        return res;
    }

    public int getHeavyNumbersCount(long fromIncl, long toIncl, int heavyThreshold) {
        return getHeavyNumbersCount(toIncl, heavyThreshold) -
                getHeavyNumbersCount(fromIncl - 1, heavyThreshold);
    }
}

它的使用方法如下：

HeavyNumbers h = new HeavyNumbers();
System.out.println( h.getHeavyNumbersCount(100000000,7));

打印出569484，未初始化表的重复计算时间在1微秒以下。

- Antonín Lejsek

---

在我编写JS版本之前，我没有注意到你的回答。我在JS中获得的速度约为0.07毫秒，因此Java显然比JS快100倍，这甚至比我预期的要好 :-) - m69 ''snarky and unwelcoming''

@m69 似乎有些问题，JS 不应该那么慢。也许我们没有以相同的方式测量时间。我制作了查找表（一次）并为 1000000 个随机 0..x 范围计算了大量数字。它在不到 1 秒的时间内完成，因此平均每次计算都不到 1 微秒。这不是完美的时间估计，但是如果没有循环进行测量，那么测量结果将会完全误导。 - Antonín Lejsek

我使用了每次重新生成查找表的方法进行测量，因为这样可以将速度与没有可重用部分的其他算法进行比较。（但我的代码有很多方面可以改进，例如我正在生成从未使用过的表的部分。） - m69 ''snarky and unwelcoming''

Answer 3

这是一个使用记忆化的基本递归，按顺序枚举固定位数数字的每个数字可能性。通过控制计算相应位数时的i范围，您可以设置A和B的值。看起来很快（请参见20位数字的结果）。

JavaScript代码：

var hash = {}
 
function f(k,soFar,count){
  if (k == 0){
    return 1;
  }

  var key = [k,soFar].join(",");
  
  if (hash[key]){
    return hash[key];
  }

  var res = 0;

  for (var i=Math.max(count==0?1:0,7*(k+count)+1-soFar-9*(k-1)); i<=9; i++){
    res += f(k-1,soFar+i,count+1);
  }

  return hash[key] = res;
}

// Output:

console.log(f(3,0,0)); // 56
hash = {};

console.log(f(6,0,0)); // 12313
hash = {};

console.log(f(20,0,0)); // 2224550892070475

- גלעד ברקן

---

它似乎在8位数字上的时钟速度约为0.333毫秒。然而，它给出的是478302而不是569484；你是否将“3位数字”解释为000、001、002...999？我们一直在使用0、1、2...999，因此8和96被认为是繁重的。 - m69 ''snarky and unwelcoming''

@m69, 我认为使用我的代码生成8位数字会得到从10000000到99999999的报告，这合理吗？我的8位和9位结果与Matt Timmermans的代码相符。（对于特定范围，我认为可以通过对i进行条件判断来控制A和B的取值。） - גלעד ברקן

啊哈，f(1,0,0)+f(2,0,0)+...+f(8,0,0)确实返回了569484，在大约0.8毫秒内完成。 - m69 ''snarky and unwelcoming''

Answer 4

我从不同的角度看待这个问题。我的看法是，问题基于数字的十进制表示，所以您应该首先将数字转换为十进制表示。可能有更好的方法，但Java字符串以十进制表示整数，因此我使用了它们。将单个字符转换为整数实际上非常快，因此这并不会花费太多时间。

最重要的是，在这件事情中，您的计算永远不需要使用除法或浮点数。该问题本质上仅涉及整数。数字（整数）中的所有数字（整数）是否加起来大于或等于七（整数）倍的位数（整数）？

注意-我不声称这是最快的方法，但这可能比您最初的方法更快。

这是我的代码：

package heavyNum;

public class HeavyNum
{
    public static void main(String[] args)
    {
        HeavyNum hn = new HeavyNum();
        long startTime = System.currentTimeMillis();
        hn.countHeavy(100000000, 1);
        long endTime = System.currentTimeMillis();
        System.out.println("Time elapsed: "+(endTime- startTime));
    }

    private void countHeavy(int A, int B)
    {
        int heavyFound = 0;
        for(int i = B+1; i < A; i++)
        {
            if(isHeavy(i))
                heavyFound++;
        }
        System.out.println("Found "+heavyFound+" heavy numbers");
    }

    private boolean isHeavy(int i)
    {
        String asString = Integer.valueOf(i).toString();
        int length = asString.length();
        int dividingLine = length * 7, currTotal = 0, counter = 0;
        while(counter < length)
        {
            currTotal += Character.getNumericValue(asString.charAt(counter++));
        }
        return currTotal > dividingLine;
    }
}

感谢这个SO问题，让我知道如何获取整数的位数，以及这个SO问题，让我知道如何快速将字符转换为Java中的整数。

在一台没有调试器的强大计算机上运行，针对1到100,000,000之间的数字，输出如下：

发现569484个重数字

经过时间：6985毫秒

编辑：最初我正在寻找其位数大于或等于7倍数字位数的数字。之前我有843453个数字的结果，用时7025毫秒。

- Jeutnarg

---

你确定toString()比重复的模除法更好吗？毕竟，toString()很可能也是这样做的。我同意只需计算数字的数量并查看最终的count > 7*numDigits是否成立即可。 - Rudy Velthuis

Java中的整数转字符串转换经过优化，速度非常快：请查看源代码：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/Integer.java。此外，我想将整数转换为字符串的主要原因是将字符作为整数提取基本上是恒定时间。这使我将复杂性隔离到Java中最优化的库之一 - 这不一定是最佳选项，但它将非常好。每秒检查14,000多个数字已足够好了。 - Jeutnarg

toString(i, 10) 的作用只是重复执行模除操作。它并不比问题中使用的代码更快（稍微方便一些），因为那个代码不仅获取了权重，还同时计算了数字的数量。它应该返回一个布尔值而不是一个浮点数。现在已经很晚了，我明天可能会发布另一种替代方案。 - Rudy Velthuis

只需看一下我的答案。走int到String再到char到int的弯路并不比我使用的简单div/mod循环更快。Java中的字符串例程实际上相当标准，肯定不是非常快的。 - Rudy Velthuis

你需要使用 curTotal > dividingLine，而不是 curTotal >= dividingLine。 - Matt Timmermans

Answer 5

你确实可以使用字符串来获取数字的数量，然后将各个数字的值相加，以查看它们的sum > 7 * length，就像Jeutnarg所做的那样。我采用了他的代码，并添加了自己简单的isHeavyRV(int)函数：

private boolean isHeavyRV(int i)
{
    int sum = 0, count = 0;
    while (i > 0)
    {
        sum += i % 10;
        count++;
        i = i / 10;
    }
    return sum >= count * 7;
}

现在，不再是

        if(isHeavy(i))

我尝试过

        if(isHeavyRV(i))

我实际上首先测试了他使用字符串实现的 isHeavy() 方法，在我的机器上（一台较旧的 iMac），它用了12388毫秒，找到了843453个重数。

使用我的实现，我找到了完全相同数量的重数，但只需要5416毫秒。

字符串可能很快，但是它们无法击败基本上做与 Integer.toString(i, 10) 相同事情的简单循环，但不需要字符串的弯路。

- Rudy Velthuis

Answer 6

当您将数字加1时，实际上是将某一位数字递增1，并将所有较低位设置为0。如果递增操作使得数字从一个重数变成了非重数，则是因为太多的低位数字被清零了。在这种情况下，很容易找到下一个重数，而无需检查中间所有的数字：

public class CountHeavy
{
    public static void main(String[] args)
    {
        long startTime = System.currentTimeMillis();
        int numHeavy = countHeavy(1, 100000000);
        long endTime = System.currentTimeMillis();
        System.out.printf("Found %d heavy numbers between 1 and 100000000\n", numHeavy);
        System.out.println("Time elapsed: "+(endTime- startTime)+" ms");
    }

    static int countHeavy(int from, int to)
    {
        int numdigits=1;
        int maxatdigits=9;
        int numFound = 0;
        if (from<1)
        {
            from=1;
        }
        for(int i = from; i < to;)
        {
            //keep track of number of digits in i
            while (i > maxatdigits)
            {
                long newmax = 10L*maxatdigits+9;
                maxatdigits = (int)Math.min(Integer.MAX_VALUE, newmax);
                ++numdigits;
            }
            //get sum of digits
            int digitsum=0;
            for(int digits=i;digits>0;digits/=10)
            {
                digitsum+=(digits%10);
            }

            //calculate a step size that increments the first non-zero digit
            int step=1;
            int stepzeros=0;
            while(step <= (Integer.MAX_VALUE/10) && to-i >= step*10 && i%(step*10) == 0)
            {
                step*=10;
                stepzeros+=1;
            }
            //step is a 1 followed stepzeros zeros

            //how much is our sum too small by?
            int need = numdigits*7+1 - digitsum;
            if (need <= 0)
            {
                //already have enough.  All the numbers between i and i+step are heavy
                numFound+=step;
            }
            else if (need <= stepzeros*9)
            {
                //increment to the smallest possible heavy number. This puts all the
                //needed sum in the lowest-order digits
                step = need%9;
                for(;need >= 9;need-=9)
                {
                    step = step*10+9;
                }
            }
            //else there are no heavy numbers between i and i+step
            i+=step;
        }
        return numFound;
    }
}

在1到100000000之间找到了569484个重数。

时间耗费：31毫秒。

请注意，答案与@JeutNarg的不同，因为您要求平均值>7，而不是平均值>=7。

- Matt Timmermans

---

目前没有投票了，但这确实是解决方案。比其他解决方案快得多，而且更加优雅。 - Rudy Velthuis

@RudyVelthuis 看来 long numHeavy = countHeavy(1111111111L, 9999999999L); 有点慢。我的程序立即输出了一个20位数的结果 ^^. :) - גלעד ברקן

是的，与其他一些解决方案相比，它速度较慢。 - Rudy Velthuis