2
\$\begingroup\$

Here is the problem statement:

Given integers \$a\$ (\$0 \le a \le 20\$) and \$b\$ (\$0 \le b \le 2,147,483,000\$), where \$a\$ and \$b\$ are not both 0, find the last digit of \$a^b\$.

Input

The first line of input contains an integer \$t\$, the number of test cases (\$t \le 30\$). \$t\$ test cases follow. For each test case will appear \$a\$ and \$b\$ separated by a space.

Output

For each test case output an integer per line representing the result.

Example Input:

2
3 10
6 2

Example Output:

9
6

Here is the code which is exceeding the time limit:

#include <stdio.h>

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int base,exponent;
        scanf("%lld%lld",&base,&exponent);
        if(base==0&&exponent==0)
        {
            printf("1\n");
        }
        else
        {
            long long int digit=1;
            long long int i;
            for(i=1;i<=exponent;i++)
            {
                digit=(base*digit)%10;
            }
            printf("%lld\n",digit);
        }
    }
    return 0;
}

How do I make this more efficient?

\$\endgroup\$
4
\$\begingroup\$

As you have probably noticed, this is not efficient because you have a loop running exponent times (which could be over 2 billion). The way to make this more efficient is not to make your code faster, but to choose a better algorithm.

I'm not going to tell you outright what the answer is, but do the following. Add some output to your loop:

        for(i=1;i<=exponent;i++)
        {
            digit=(base*digit)%10;
            printf("digit = %d\n", digit);
        }

and then run your program for some (small) sample inputs. You should notice a pattern. The key is to identify the pattern and use it to avoid running the loop a billion times.

\$\endgroup\$

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.