Skip to main content
add signed int
Source Link
rolfl
  • 97.5k
  • 17
  • 218
  • 418

I have used simple int variables because there's no need for more precision on the basic digits, carry, or inputs. The only place where more precision is needed is for the sum, where, with some unlikely power that has 4000 digits of 9, will sum to 36000, which is larger than can fit in a signed 16-bit value, but unsigned is fine. On further reflection, the largest power will be significantly less than 4000 digits, at most \$9^{4000}\$ which will be about 3600 digits in total, with at worst case all being 9's (they are not), will be less than 32768. So, a signed int will be fine for the sum too.

I have used simple int variables because there's no need for more precision on the basic digits, carry, or inputs. The only place where more precision is needed is for the sum, where, with some unlikely power that has 4000 digits of 9, will sum to 36000, which is larger than can fit in a signed 16-bit value, but unsigned is fine.

I have used simple int variables because there's no need for more precision on the basic digits, carry, or inputs. The only place where more precision is needed is for the sum, where, with some unlikely power that has 4000 digits of 9, will sum to 36000, which is larger than can fit in a signed 16-bit value, but unsigned is fine. On further reflection, the largest power will be significantly less than 4000 digits, at most \$9^{4000}\$ which will be about 3600 digits in total, with at worst case all being 9's (they are not), will be less than 32768. So, a signed int will be fine for the sum too.

Source Link
rolfl
  • 97.5k
  • 17
  • 218
  • 418

Simple method extraction will help a lot with your code. Additionally, you create a number of variables that are unreasonably large... why do you need long long values?

The conditions for the program are clear, that the input cases will be relatively few, and that the base and power are small too (the base is <= 10, and the power is <= 4000).

Notice how you can allocate the digits array inside the method call, and that there's no need to over-allocate the array. This makes the methods reusable and re-entrant. The main method handles the user interaction, and the rest of the logic is extracted in to self-standing calls.

I have used simple int variables because there's no need for more precision on the basic digits, carry, or inputs. The only place where more precision is needed is for the sum, where, with some unlikely power that has 4000 digits of 9, will sum to 36000, which is larger than can fit in a signed 16-bit value, but unsigned is fine.

All up, the code can be simplified as:

#include<stdio.h>

int multiply (int *digits, const int len, const int mult) {
    int carry = 0;
    for (int i = 0; i < len; i++) {
        digits[i] *= mult;
        digits[i] += carry;
        carry = digits[i] / 10;
        digits[i] %= 10;
    }
    if (carry) {
        digits[len] = carry;
        return len + 1;
    }
    return len;
}

unsigned int sumPower(const int base, const int power) {
    int digits[power + 1];
    digits[0] = 1;
    int len = 1;
    for (int i = 1; i <= power; i++) {
        len = multiply(digits, len, base);
    }
    unsigned int sum = 0;
    while (--len >= 0) {
        sum += digits[len];
    }
    return sum;
}

int main() {
    int tests,a,b,newVar ;
    scanf("%d",&tests) ;
    newVar=1 ;
    while(tests--) {
        scanf("%d %d",&a,&b) ;
        printf("Case %d: %d to %d -> %u\n", newVar, a, b, sumPower(a, b)) ;
        newVar++ ;
    }
    return 0 ;
}