0
\$\begingroup\$

As a follow up to my post here. Please refer to the problem statement in that post.

I have edited this code to make it time efficient, but doing so the size of the source file has crossed the limit of 700 bytes. How do I reduce the file size?

#include <stdio.h>

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int base,exponent;
        scanf("%lld%lld",&base,&exponent);
        if(exponent==0)
        {
            printf("1\n");
        }
        else
        {
            int i;
            int dig[5];
            dig[0]=1;
            for(i=1;i<=4;i++)
            {
                dig[i]=(base*dig[i-1])%10;
            }
            if(exponent%4==0)
                printf("%d\n",dig[4]);
            else if(exponent%4==1)
                printf("%d\n",dig[1]);
            else if(exponent%4==2)
                printf("%d\n",dig[2]);
            else if(exponent%4==3)
                printf("%d\n",dig[3]);
        }
    }
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$
        if(exponent%4==0)
            printf("%d\n",dig[4]);
        else if(exponent%4==1)
            printf("%d\n",dig[1]);
        else if(exponent%4==2)
            printf("%d\n",dig[2]);
        else if(exponent%4==3)
            printf("%d\n",dig[3]);

can be written (storing value in variable)

        int exp_mod = exponent%4;
        if(exp_mod==0)
            printf("%d\n",dig[4]);
        else if(exp_mod==1)
            printf("%d\n",dig[1]);
        else if(exp_mod==2)
            printf("%d\n",dig[2]);
        else if(exp_mod==3)
            printf("%d\n",dig[3]);

which can be written (replacing hard-coded value)

        int exp_mod = exponent%4;
        if(exp_mod==0)
            printf("%d\n",dig[4]);
        else
            printf("%d\n",dig[exp_mod]);

which can be written (using a single printf)

        int exp_mod = exponent%4;
        int index = (exp_mod==0) ? 4 : exp_mod;
        printf("%d\n",dig[index]);

Maybe this could be written using mathematical tricks but it's already much shorter (and you could remove the index variable).

\$\endgroup\$
3
\$\begingroup\$

It really isn't that hard to bring your code under 700 bytes. Just replacing base and exponent with a and b, respectively, would do the trick. Normally, such renaming would hurt readability. But here, you are just matching the terminology in the question, which arguably improves intelligibility.

You can also trim obvious fat, such as

  • eliminating the implicit return 0
  • long instead of long long int
  • switching to a more efficient brace style

The cases at the end can all be collapsed using a bit of modulo arithmetic.

There is plenty of room within 700 bytes for writing nice code. You can expand dig into digit. You can add customary spaces around operators for readability. You can even write a long explanatory comment.

#include <stdio.h>

/*
The last digit of pow(a, b) cycles with b modulo 4.

0, 0, 0, 0, 0, ...
1, 1, 1, 1, 1, ...
2, 4, 8, 6, 2, ...
3, 9, 7, 1, 3, ...
4, 6, 4, 6, 4, ...
5, 5, 5, 5, 5, ...
6, 6, 6, 6, 6, ...
7, 9, 3, 1, 7, ...
8, 4, 2, 6, 8, ...
9, 1, 9, 1, 9, ...
*/
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long a, b;
        scanf("%ld%ld", &a, &b);
        if (b == 0) {
            printf("1\n");
        } else {
            int i;
            int digit[4];
            digit[0] = 1;
            for (i = 1; i <= 4; i++) {
                digit[i % 4] = (a * digit[i - 1]) % 10;
            }
            printf("%d\n", digit[b % 4]);
        }
    }
}

And we haven't even touched truly nefarious tricks like replacing spaces with tabs, which would save another hundred bytes!

\$\endgroup\$
  • \$\begingroup\$ in the last printf statement if b%4 is 0 you wouldn't get the right output, because 0%4 and 4n%4 are both zero and corresponding last digit may not be same \$\endgroup\$ – Atul Shanbhag Apr 21 '15 at 12:00
  • \$\begingroup\$ Do you have a specific counterexample? The b == 0 case is already handled separately, right? \$\endgroup\$ – 200_success Apr 21 '15 at 12:03
  • \$\begingroup\$ okay i see you have digit[i%4] , sorry my bad \$\endgroup\$ – Atul Shanbhag Apr 21 '15 at 12:05
2
\$\begingroup\$

You already figured out that the last digit of \$ a^b \$ is equal to the last digit of \$ a^c \$ where \$ c \$ is a "reduced exponent" in the range \$ 0, \ldots, 4 \$. Except for the special case \$ b = 0 \$, this reduction can be computed as \$ c = (b - 1) \bmod 4 + 1 \$.

Btw, this is an immediate consequence of Fermat's little theorem.

If you reduce the exponent first, then you don't have to pre-compute the dig[5] array, instead you compute \$ a^c \$ with a repeated multiplication (as in your previous question).

From the given bounds \$0 \le a \le 20\$ and \$0 \le b \le 2,147,483,000\$, and assuming that int is a 32-bit integer (which is the case on all modern platforms), it follows that all intermediate values and results fit into an int, and long long int is not needed.

This gives the following implementation, where the actual computation is moved to a separate function for better readability:

#include <stdio.h>

static int lastPowerDigit(int base, int exp)
{
    if (exp > 0) {
        exp = (exp - 1) % 4 + 1;
    }
    int result = 1;
    for (int i = 1; i <= exp; i++) {
        result *= base // base<=20, exp<=4, so this does not overflow
    }
    return result % 10;
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--) {
        int base, exponent;
        scanf("%d%d", &base, &exponent);
        printf("%d\n", lastPowerDigit(base, exponent));
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I agree that long long is overkill. But why assume that int is 32 bits? Just use long like you're supposed to (or int32_t, but that makes the scanf uglier). \$\endgroup\$ – 200_success Apr 21 '15 at 10:33
  • \$\begingroup\$ @200_success: Good point. (Even if I don't know any platform – apart from things like embedded systems – where int is not 32 bit.) I would have updated my answer, but now you have written your own answer, and I don't want to give the impression of "copying ideas". \$\endgroup\$ – Martin R Apr 21 '15 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.