找到8位数字的总和的有效方法

Question

我必须找到前4位数的总和,最后4位数的总和并比较它们(m和n之间的所有数字).但是,当我在线提交我的解决方案时,时间限制存在问题.

这是我的代码:

#include <stdio.h>

int main()
{
    int M, N, res = 0, cnt, first4, second4, sum1, sum2;

    scanf("%d", &M);
    scanf("%d", &N);

    for(cnt = M; cnt <= N; cnt++)
    {
        first4 = cnt % 10000;
        sum1 = first4 % 10 + (first4 / 10) % 10 + (first4 / 100) % 10 + (first4 / 1000) % 10;
        second4 = cnt / 10000;
        sum2 = second4 % 10 + (second4 / 10) % 10 + (second4 / 100) % 10 + (second4 / 1000) % 10;

        if(sum1 == sum2)
            res++;

    }

    printf("%d", res);


    return 0;
}

我正试图找到一种更有效的方法来做到这一点.

Answer 1

我不知道这是否会明显更快,但您可以尝试将数字分成两个4位数字,然后使用表格查找来获得总和.这样,只有一个除法运算而不是八个.

您可以预先计算10000个总和的表,以便进行编译,因此根本没有运行时成本.

可以使用的另一个稍微复杂但可能更快的方法是具有10000个元素的表或映射,这与求和表的反向相反,您可以将总和映射到将产生该总和的四位数字的集合. .这样,当您必须找到特定范围10000数字范围的结果时,它是对最重要的四位数之和的简单查找.例如,要查找范围12340000 - 12349999的结果,可以在反向查找表上使用二进制搜索来快速查找0 - 9999范围内有多少数字10(1 + 2 + 3 + 4) .

同样 - 这个反向和查找表可以预先计算并作为静态数组编译.

以这种方式,完成10000个数字范围的结果通过几个二进制搜索来执行.由于必须忽略来自感兴趣范围之外的匹配,因此也可以使用反向查找表来处理任何部分范围,并且稍微复杂一些.但是这种并发症只需要在整个子范围集中最多发生两次.

这会将算法的复杂度从O(N*N)降低到O(N log N)(我认为).

更新:

这是我得到的一些时间(Win32-x86,使用VS 2013(MSVC 12)和发布版本默认选项):

       range    range     
       start    end        count    time
================================================

alg1(10000000, 99999999): 4379055, 1.854 seconds
alg2(10000000, 99999999): 4379055, 0.049 seconds
alg3(10000000, 99999999): 4379055, 0.001 seconds

有:

• alg1() 是问题的原始代码
• alg2() 是我的第一个削减建议(查找预先计算的总和)
• alg3() 是第二个建议(使用按总和排序的表的和匹配的二进制搜索查找)

我在的区别实际上惊讶alg1()于alg2()

Answer 2

最后,如果你仍然感兴趣,有一个更快的方法来做到这一点.您的任务并不特别要求您计算所有数字的总和,它只询问一些特殊数字的数量.在这种情况下,诸如记忆或动态编程之类的优化技术非常方便.

在这种情况下,当你有一些数字的前四位数(让它们是1234)时,你计算它们的总和(在这种情况下为10)并且你立即知道,应该是其他四位数的总和是多少.

产生和10的任何4位数字现在可以是创建有效数字的另一半.因此,以1234开头的有效数字的总数正好是给出总和10的所有四位数字的数量.

现在考虑另一个数字,比如3412.这个数字也等于10,因此任何完成1234的右边也完成3412.

这意味着以3412开头的有效数字的数量与以1234开头的有效数字的数量相同,而有效数字的总数与有效数字的总数相同,其中前半部分产生总和10.

因此,如果我们为每个i产生总和的四位数字的数量进行预计算i,我们将知道每个前四位数字完成有效数字的最后四位数的确切组合数,而不必迭代其中的所有10000个数字 .

以下是该算法的实现

1. 预计算前半部分的每个总和的不同结束部分的数量
2. 在三个子区间中分割[M,N]区间,因为在第一个和最后一个区间不是每个结束都是可能的

该算法以比初始实现更快的方式运行(足够大N-M).

#include <string.h>

int sum_digits(int number) {
    return number%10 + (number/10)%10 + (number/100)%10 + (number/1000)%10;
}

int count(int M, int N) {
    if (M > N) return 0;

    int ret = 0;
    int tmp = 0;

    // for each i from 0 to 36 precompute number of ways we can get this sum
    // out of a four-digit number
    int A[37];
    memset(A, 0, 37*4);
    for (int i = 0; i <= 9999; ++i) {
        ++A[sum_digits(i)];
    }

    // nearest multiple of 10000 greater than M
    int near_M = ((M+9999)/10000)*10000;

    // nearest multiple of 10000 less than N
    int near_N = (N/10000)*10000;

    // count all numbers up to first multiple of 10000
    tmp = sum_digits(M/10000);
    if (near_M <= N) {
        for (int i = M; i < near_M; ++i) {
            if (tmp == sum_digits(i % 10000)) {
                ++ret;
            }
        }
    }

    // count all numbers between the 10000 multiples, use the precomputed values
    for (int i = near_M / 10000; i < near_N / 10000; ++i) {
        ret += A[sum_digits(i)];
    }

    // count all numbers after the last multiple of 10000
    tmp = sum_digits(N / 10000);
    if (near_N >= M) {
        for (int i = near_N; i <= N; ++i) {
            if (tmp == sum_digits(i % 10000)) {
                ++ret;
            }
        }
    }

    // special case when there are no multiples of 10000 between M and N
    if (near_M > near_N) {
        for (int i = M; i <= N; ++i) {
            if (sum_digits(i / 10000) == sum_digits(i % 10000)) {
                ++ret;
            }
        }
    }

    return ret;
}

编辑:我修复了评论中提到的错误.