A problem from a programming competition... Digit Sums

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 n开发者_如何学JAVAumbers 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.

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

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

This is not the complete solution (no input parsing). To get the number in base B, repeatedly take the modulo B, and then divide by B until the result is 0. This effectively computes the base-B digit from the right, and then shifts the number right.

int A,B,C; // from input
for (int x=1; x<A; x++)
{
    int sumDigits = 0;
    int v = x;
    while (v!=0) {
       sumDigits += (v % B);
       v /= B;
    }
    if (sumDigits==C)
       cout << x;
}

This is a brute force approach. It may be possible to compute this quicker by determining which sets of base B digits add up to C, arranging these in all permutations that are less than A, and then working backwards from that to create the original number.

Yum.

Try this:

int number, digitSum, resultCounter = 0;

for(int i=1; i<=A, i++)
{
   number = i; //to avoid screwing up our counter
   digitSum = 0;
   while(number > 1)
   {
      //this is the next "digit" of the number as it would be in base B; 
      //works with any base including 10.
      digitSum += (number % B);
      //remove this digit from the number, square the base, rinse, repeat 
      number /= B;
   }
   digitSum += number;

   //Does the sum match?       
   if(digitSum == C)
      resultCounter++;
}

That's your basic algorithm for one line. Now you wrap this in another For loop for each input line you received, preceded by the input collection phase itself. This process can be simplified, but I don't feel like coding your entire answer to see if my algorithm works, and this looks right whereas the simpler tricks are harder to pass by inspection.

The way this works is by modulo dividing by powers of the base. Simple example, 1234 in base 10:

1234 % 10 = 4
1234 / 10 = 123 //integer division truncates any fraction
123 % 10 = 3 //sum is 7
123 / 10 = 12
12 % 10 = 2 //sum is 9
12 / 10 = 1 //end condition, add this and the sum is 10

A harder example to figure out by inspection would be the same number in base 12:

1234 % 12 = 10 //you can call it "A" like in hex, but we need a sum anyway
1234 / 12 = 102
102 % 12 = 6 // sum 16
102/12 = 8
8 % 12 = 8 //sum 24
8 / 12 = 0 //end condition, sum still 24.

So 1234 in base 12 would be written 86A. Check the math:

8*12^2 + 6*12 + 10 = 1152 + 72 + 10 = 1234

Have fun wrapping the rest of the code around this.