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

Question

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;

}

Answer 1

Taking in account that

1. If c > 9 + 9 + 9 = 27, counter = 0.
2. counter(a, b) = counter(1, b) - counter(1, a).

We may conclude that you have only 1014*27 = 27378 possible inputs. This means that you can calculate each of 27378 values in advance, store them in an array and reduce the function to an argument range check, 2 table lookups and 1 subtraction. This should be the fastest solution possible :)

Answer 2

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.

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

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

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

Then

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

Prints:

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...

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).

Live Demo

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