Last Digit of exponent(a^b).

This is an editorial for the problem LASTDIG on SPOJ.

The problem asks us to find the last digit of the exponent a^b. It has many different ways to get solution.

Lets discuss three different approaches in solving this problem:

  • 1) Keep on multiplying the number ‘a’ for ‘b’ times and keep tracking the last digit that is to output in the end. Keeping track of last digit here implies, for larger values of ‘a’ and ‘b’, the product could cross the range of int or long.It takes a O(n) complexity. This could take a long time and might result in TLE(Time Limit Exceeded) as the limits in general to such a problem will be given to test for a faster approach that are discussed in other methods discussed below.
  • 2) Another approach to this problem could be this, with worst possible complexity being O(log n). For this we can keep squaring the number ‘a’ till the power(p) it raised to is the closest to ‘b’ and for the remaining (b-p) times, a is to be multiplied and and the last digit is finally printed out. A algorithm for this approach is
    long long int Fast_pow(long long int b, long long int e){
        long long int ans = 1;
        while (e > 0){
            if (e % 2 == 1)
                ans = (ans * b);
            e = e >> 1;
            b = (b * b);
        }
        return ans;
    }
    

    prod%10 is the answer.
    This method runs a lot faster than previous version. But the problem you start realising is for larger values of a and b, we are not allowed to store such big resultant product values in few languages. We can at most store a 64 bit value if we are using C/C++.

  • 3)In this method let us first know few facts that arises in calculating the last digit of a^b. On observing different exponents, we can say these few cases:
    – If last digit of a is ‘0’ or ‘1’ or ‘5’ or ‘6’, then always in powers of those numbers for any case of ‘b'(except b=0), last digit will be same.
    – If last digit of ‘a’ is 2, the sequence {6,2,4,8} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 3, the sequence {1,3,9,7} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 4, the sequence {6,4} follows for mod(2) of ‘b’.
    – If last digit of ‘a’ is 7, the sequence {1,7,9,3} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 8, the sequence {6,8,4,2} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 9, the sequence {1,9} follows for mod(2) of ‘b’.
    Note: for b=0, answer should be 1 in any case of ‘a’. So here we can make a switch case program or if-else program to get the answer. This approach has a O(1) complexity.

    Related Problems : Arithmancy Challenge (HackerEarth), Last Digit (SPOJ). In the problem that is asked in SPOJ, you cannot use switch case as it exceeds size limit(700 bytes). In that case try solving it by using a 2D array. It cuts down the size of the code and thus could get an accepted submission. 🙂

Advertisements