Problem with programming ... Digit Sums

Question

I need help solving Problem N from this earlier competition :

Problem N: sums of digits

Given 3 positive integers A, B and C, find the number of positive integers less than or equal to A, if it is expressed in base B, have numbers that add up to C.

The input will consist of a series of lines, each of which contains 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 spaces. The entry ends with a line containing three zeros.

The output will be the number of numbers for each input line (it must be specified in base 10).

Input example

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

Relevant Rules:

• , .. stdin, System.in, cin . , .

• , .. stdout, System.out, cout . stderr. , , conio, Crt - . . - , , , . , !

• , 32- . .

, , , , , - , .

, .

Answer 1

: 1 A. , , : O(length of A), O(log(A)).

• 10. .
• , . , .

, . Java, #/++ - . , - , .

// 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 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 iterate over all possible values of last digit
    for (int digit = 0; digit < 10; ++digit) {
        result += count(num, sum - digit);
    }

    return result;
}

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

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

, A, . ( A C.)

, A == 1000000000 : . A == 10^1000.

, , . ( Java, hashtables -). - , , .

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

memoized , Rybak, , :

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

Answer 3

( ). B, B, B , 0. base-B , .

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

. , , , B C, , A, , .

Answer 4

Yum.

:

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

. For , . , , , , , .

, . : 1234 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

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.

, 1234 12 86A. :

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

, .