Sum of digits in a^b I'm trying to calculate a problem which requires sum of digits in \$a^b\$, where \$0 \le a \le 9\$ and \$0 \le b \le 4000\$.

I have seen various other posts similar to this, but I haven't acquired best way. I have created this:

#include&lt;stdio.h&gt;
int main() {
    int digits[4000]={0} ;
    long long int test,a,b,temp,newVar ;
    scanf("%lld",&amp;test) ;
    newVar=1 ;
    while(test--) {
        scanf("%lld %lld",&amp;a,&amp;b) ;
        if(b==0) {
            printf("Case %lld: 0\n",newVar) ;
            newVar++ ;
            continue ;
        }
        b=b-1 ;
        digits[0]=a ;
        long long int len=1,carry=0,i ;
        while(b--) {
            carry=0 ;
            for(i=0 ; i&lt;len  ; i++) {
                temp=digits[i]*a + carry ;
                digits[i]=temp%10;
                carry=temp/10 ;
            }
            if(carry!=0) {
                digits[i]=carry ;
                len++ ;
            }
        }
        long long int sum=0 ;
        for(i=len-1 ; i&gt;=0 ; i--)
            sum+=digits[i] ;
        printf("Case %lld: %llu\n",newVar,sum) ;
        newVar++ ;
    }
    return 0 ;
}


I tested my code for large powers, which is giving the right results.

For example:

Input:




3
2 32
3 2
2 60



Output:


Case 1: 58
Case 2: 9
Case 3: 82



Is there any way to increase the speed or running time of this code? I have a time limit of 1 sec and this code is showing Time Limit Exceeded.

This is not a contest that is going to effect my(or anyone else) ratings. For me, it's a way to learn new things. So any help will be appreciated.
Some general remarks:


Use more and consistent spacing, e.g.

digits[i]=temp%10;


should be

digits[i] = temp % 10;

Define variables only at the scope where they are used, e.g. carry 
is used only inside the while (b--) { ... } loop.
Move the actual computation to a separate function so that main() becomes 
shorter. That makes it also easier to add test cases.
Assuming that int has (at least) 32 bits (which is the case on all modern
platforms), there is no need to use long long at all in your code.
There is no need to treat the case b = 0 separately. a ^ 0 is 1, and that can be covered with the general case if you
start with digits[] = { 1 } instead of digits[] = { a }.


The performance can be increased by storing more than a single decimal
digit in each array element digits[i]. Since 10^9 &lt; 2^31, you can store
8 decimal digits in digits[i] and digits[i] * a + carry will still not
overflow.

Your program would then look like this:

const int BASE = 100000000; //  10^8

int powerDigitSum(int a, int b) {
    int digits[4000] = { 1 } ;
    int len = 1;

    while (b-- &gt; 0) {
        int carry = 0;
        for (int i = 0; i &lt; len; i++) {
            int temp = digits[i] * a + carry;
            digits[i] = temp % BASE;
            carry = temp / BASE;
        }
        if (carry != 0) {
            digits[len++] = carry;
        }
    }

    int sum = 0;
    for (int i = 0; i &lt; len; i++) {
        int d = digits[i];
        while (d &gt; 0) {
            sum += d % 10;
            d /= 10;
        }
    }
    return sum;
}

int main() {
    int test, a, b;
    scanf("%d",&amp;test) ;
    for (int i = 0; i &lt; test; i++) {
        scanf("%d %d",&amp;a,&amp;b) ;
        int sum = powerDigitSum(a, b) ;
        printf("Case %d: %d\n", i, sum) ;
    }
    return 0 ;
}


Your original algorithm corresponds to BASE = 10. Using BASE = 100000000
instead reduced the computation time for a=9, b=4000 from 0.095 seconds
to 0.014 seconds on my computer.

If that is not sufficient, you can use (unsigned) long long for the digits[] array  and work with an even larger BASE.