如何有效地找到数字中的数字加起来为特定数字的范围内的数字数 [英] How do I efficiently find the number of digits within a range in which the digits within the number add up to a specific number

问题描述

我得到了 a、b 和 c.a - b 是范围，c 是所需的数字所需的输出是范围内的数字加起来为 c 的数字的数量.这些是条件:(1 ≤ A ≤ B <1015, 1 ≤ C ≤ 135)我当前的代码使用

I am given a, b, and c. a - b is the range and c is the desired number the required output is the number of numbers within the range that have digits that add up to c. these are the conditions: (1 ≤ A ≤ B < 1015, 1 ≤ C ≤ 135) my current code utilises

while (num != 0){
            sum = sum + num % 10;
            num = num / 10;
        }

但是实现完全正确的答案太慢了；

but it is too slow to achieve the full correct answer;

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    long long int a, b, c;
    long long int sum = 0;
    long long int num;
    long long int finalone;
    long long int counter = 0;
    string arr[b];
    cin >> a >> b >> c;
    for (long long int x=a; x<b; x++){
        num = x;
        while (num != 0){
            sum = sum + num % 10;
            num = num / 10;
        }
        if (sum == c && counter == 0){
            finalone = x;
        }
        if (sum == c){
            counter++;
        }
        sum = 0;
    }
    cout << counter << endl;
    cout << finalone;

}

推荐答案

首先，请注意您的问题陈述有点可疑.如果您考虑到 1015 以内的数字，那么您可以获得的最大数字总和来自 999 和 27.因此，我们已经知道有多少个数字的总和为 27 <c <= 135 ;).

First of all, note that your problem statement is a bit fishy. If you consider numbers up to 1015 then the biggest sum of digits you can get is from 999 and is 27. Hence, we already know how many number have a sum of 27 < c <= 135 ;).

接下来，您的算法会进行一些不必要的计算.对于范围内的每个数字，当大多数情况下只有一个数字发生变化时，您可以使用模数重新计算每个数字.如果将数字存储在数组中，手动"增加数字并将数组元素相加，则可以改进代码.虽然，这不会提高复杂性.

Next, your algorithm does quite some unnecessary computations. For each number in the range you use modulo to recalculate each single digit when most of the time only a single digit changes. Your code could be improved if you stored the digits in an array, increment the number "manually" and add up the array elements. Though, this wont improve complexitiy.

尝试从不同的角度看待问题.您基本上必须找到四位数字的组合，使得 w+x+y+z = c 和这些数字的串联"落在 [a,b].例如当 c==4 那么只有几个组合:

Try to look at the problem from a different perspective. You basically have to find combinations of four digits such that w+x+y+z = c and the "concatenation" of these digits falls withint the range [a,b]. For example when c==4 then there are only few combinations:

1111, 211, 121, 112, 31, 22, 13

一旦您有了这些数字，就可以直接计算其中有多少属于给定范围.

Once you have those numbers it is straight-forward to count how many of them fall into the given range.

为了好玩，我决定看看是否可以实现蛮力策略以在编译时计算.我们可以这样计算数字的总和:

For the fun of it I decided to see if the brute force strategy can be implemented to be computed at compile time. We can calculate the sum of digits like this:

template <int x> 
using number = std::integral_constant<int,x>;

template <int x>
struct sum_of_digits : number< sum_of_digits<x/10>::value + (x%10)> {};

template <> 
struct sum_of_digits<0> : number<0> {};

我使用助手来检查两个整数是否相等

I use a helper to check if two integers are equal

template <int x,int y>
struct equals : std::false_type {};

template <int x>
struct equals<x,x> : std::true_type {};

将两者放在一起，我们可以检查一个数字是否具有给定的数字总和:

Putting both together we can check if a number has a given sum of digits:

template <int x,int c>
struct is_sum_of_digits : equals<c,sum_of_digits<x>::value> {};

现在我们用 [0,a] 中正确的数字总和来计算数字:

Now we count numbers with the correct sum of digits in [0,a] :

template <int a,int c> 
struct count : number<is_sum_of_digits<a,c>::value + count<a-1,c>::value> {};

template <int c> 
struct count<0,c> : number<0> {};

就示例而言，我最多只使用三位数.限制是我使用的 std::index_sequence 的模板递归.您可能需要启动您的 -ftemplate-depth 以将其编译为更多数字，并且我不得不展开其中一个维度以免达到我的编译器限制.使用编译时结果，我填写了一个查找表以在运行时获取结果:

For the sake of the example I use only up to three digits numbers. The limit is the template recursion from the std::index_sequence I am using. You may have to crank up your -ftemplate-depth to get it compiled for more digits and I had to unroll one of the dimensions not to hit my compilers limit. With the compile time results I fill a lookup table to get the results at runtime:

const int max_b = 100; // max sum of digits is 18 for 99
template <std::size_t ... is>
int get_number_of_correct_sum_impl(int a,int b,int c,std::index_sequence<is...>){

    static constexpr int table[] = { count<is,0>::value...,
         count<is,1>::value... , count<is,2>::value... ,
         count<is,3>::value... , count<is,4>::value... ,
         count<is,5>::value... , count<is,6>::value...,
         count<is,7>::value... , count<is,8>::value... ,
         count<is,9>::value... , count<is,10>::value... ,
         count<is,11>::value... , count<is,12>::value... ,
         count<is,13>::value... , count<is,14>::value... ,
         count<is,15>::value... , count<is,16>::value... ,
         count<is,17>::value... , count<is,18>::value...                                                                   
    };
    auto index = [max_b = max_b](int a,int c){ return c*max_b + a; };
    return table[index(b,c)] - table[index(a,c)];
}

int get_number_of_correct_sum(int a,int b,int c){
    return get_number_of_correct_sum_impl(a,b,c,std::make_index_sequence<max_b>{});
}

然后

int main() {
    for (int i=1;i<33;++i){
        std::cout << i << " " << get_number_of_correct_sum(0,i,5) << "\n";
    }
}

打印:

1 0
2 0
3 0
4 0
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 2
15 2
...etc...

请注意，这仍然是简单的蛮力检查所有数字并计算满足条件的数量，但它是在编译时完成的.运行时剩下的就是在查找表中查找两个条目并取它们的差值，即 O(1).

Note that this is still simply brute force checking all numbers and counting how many fulfill the condition, but it is done at compile time. All that is left at runtime is to look up the two entries in the look up table and taking their difference, ie O(1).

现场演示

PS:关于查找表的帮助的积分转至 https://stackoverflow.com/a/55543931/4117728 和 https://stackoverflow.com/a/55543946/4117728

PS: Credits for help with the lookup table goes to https://stackoverflow.com/a/55543931/4117728 and https://stackoverflow.com/a/55543946/4117728

这篇关于如何有效地找到数字中的数字加起来为特定数字的范围内的数字数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！