A problem from a programming competition... Digit Sums

Question

I need help solving problem N from this earlier competition:

Problem N: Digit Sums

Given 3 positive integers A, B and C, find how many positive integers less than or equal to A, when expressed in base B, have digits which sum to C.

Input will consist of a series of lines, each containing three integers, A, B and C, 2 ≤ B ≤ 100, 1 ≤ A, C ≤ 1,000,000,000. The numbers A, B and C are given in base 10 and are separated by one or more blanks. The input is terminated by a line containing three zeros.

Output will be the number of numbers, for each input line (it must be given in base 10).

Sample input

100 10 9
100 10 1
750000 2 2
1000000000 10 40
100000000 100 200
0 0 0

Sample output

10
3
189
45433800
666303

The relevant rules:

1. Read all input from the keyboard, i.e. use stdin, System.in, cin or equivalent. Input will be redirected from a file to form the input to your submission.

2. Write all output to the screen, i.e. use stdout, System.out, cout or equivalent. Do not write to stderr. Do NOT use, or even include, any module that allows direct manipulation of the screen, such as conio, Crt or anything similar. Output from your program is redirected to a file for later checking. Use of direct I/O means that such output is not redirected and hence cannot be checked. This could mean that a correct program is rejected!

3. Unless otherwise stated, all integers in the input will fit into a standard 32-bit computer word. Adjacent integers on a line will be separated by one or more spaces.

Of course, it's fair to say that I should learn more before trying to solve this, but i'd really appreciate it if someone here told me how it's done.

Thanks in advance, John.

Answer 1

Other people pointed out trivial solution: iterate over all numbers from 1 to A. But this problem, actually, can be solved in nearly constant time: O(length of A), which is O(log(A)).

1. Code provided is for base 10. Adapting it for arbitrary base is trivial.
2. To reach above estimate for time, you need to add memorization to recursion. Let me know if you have questions about that part.

Now, recursive function itself. Written in Java, but everything should work in C#/C++ without any changes. It's big, but mostly because of comments where I try to clarify algorithm.

// returns amount of numbers strictly less than 'num' with sum of digits 'sum'
// pay attention to word 'strictly'
int count(int num, int sum) {
    // no numbers with negative sum of digits
    if (sum < 0) {
        return 0;
    }

    int result = 0;

    // imagine, 'num' == 1234
    // let's check numbers 1233, 1232, 1231, 1230 manually
    while (num % 10 > 0) {
        --num;

        // check if current number is good
        if (sumOfDigits(num) == sum) {
            // one more result
            ++result;
        }
    }

    if (num == 0) {
        // zero reached, no more numbers to check
        return result;
    }

    num /= 10;

    // Using example above (1234), now we're left with numbers
    // strictly less than 1230 to check (1..1229)
    // It means, any number less than 123 with arbitrary digit appended to the right
    // E.g., if this digit in the right (last digit) is 3,
    // then sum of the other digits must be "sum - 3"
    // and we need to add to result 'count(123, sum - 3)'

    // let's iterate over all possible values of last digit
    for (int digit = 0; digit < 10; ++digit) {
        result += count(num, sum - digit);
    }

    return result;
}

Helper function

// returns sum of digits, plain and simple
int sumOfDigits(int x) {
    int result = 0;
    while (x > 0) {
        result += x % 10;
        x /= 10;
    }
    return result;
}

Now, let's write a little tester

    int A = 12345;
    int C = 13;

    // recursive solution
    System.out.println(count(A + 1, C));

    // brute-force solution 
    int total = 0;
    for (int i = 1; i <= A; ++i) {
        if (sumOfDigits(i) == C) {
            ++total;
        }
    }
    System.out.println(total);

You can write more comprehensive tester checking all values of A, but overall solution seems to be correct. (I tried several random A's and C's.)

Don't forget, you can't test solution for A == 1000000000 without memorization: it'll run too long. But with memorization, you can test it even for A == 10^1000.

edit
Just to prove a concept, poor man's memorization. (in Java, in other languages hashtables are declared differently) But if you want to learn something, it might be better to try to do it yourself.

// hold values here
private Map<String, Integer> mem;

int count(int num, int sum) {
    // no numbers with negative sum of digits
    if (sum < 0) {
        return 0;
    }

    String key = num + " " + sum;
    if (mem.containsKey(key)) {
        return mem.get(key);
    }

    // ... 
    // continue as above...
    // ...

    mem.put(key, result);
    return result;
}

Answer 2

Here's the same memoized recursive solution that Rybak posted, but with a simpler implementation, in my humble opinion:

HashMap<String, Integer> cache = new HashMap<String, Integer>();

int count(int bound, int base, int sum) {
    // No negative digit sums.
    if (sum < 0)
        return 0;

    // Handle one digit case.
    if (bound < base)
        return (sum <= bound) ? 1 : 0;

    String key = bound + " " + sum;
    if (cache.containsKey(key))
        return cache.get(key);

    int count = 0;
    for (int digit = 0; digit < base; digit++)
        count += count((bound - digit) / base, base, sum - digit);

    cache.put(key, count);
    return count;
}