CODEWITHSUNDEEP
number-theory
Nairit
Nairit

Reputation: 163

Most efficient way to find the last digit of a^b

I am a python newbie. I am looking to compute (a ** b) % 10 in the most efficient way possible (i.e. simplifying the power part). I have found one way to do this: ((a % 10) ** b) % 10. My question is, are there more efficient ways to do this? This problem is an extension of a CodeFights task. The original problem accepted (a ** b) % 10.

Upvotes: 1

Views: 540

Answers (2)

Tobias Ribizel
Tobias Ribizel

Reputation: 5421

  • Since the numbers mod 10 form a ring, you can compute the residue mod 10 at every intermediate value without influencing the result.

  • There is a O(log b) step algorithm called Square-and-multiply that can drastically speed up your computations.

    The basic idea is that for even b, we can just square the argument and divide the exponent by 2 without changing the result. For odd b, we extract one power of a (or our current argument) and proceed like in the even case (squaring and halving).

So putting this together, if you implement the Square-and-multiply algorithm and compute the residue mod 10 after every step, you will have a nice and efficient way to compute your last digit.

Upvotes: 1

HiddenHopes
HiddenHopes

Reputation: 63

  • step 1: Take the inputs a and b as character string
  • step 2:
    • convert only the last character of a into integer and store in a variable say m.
    • convert only the last two character of b into integer and store in a variable say n. If b is a single character, then convert this character only.
  • step 3: find x. if n % 4 == 0: x = 4 else: x = n % 4
  • step 4: last_digit = (m ** x) % 10

Short Explanation: If you list out the initial expansions of a power, you will find a pattern. So we can reduce a and b to m and x respectively. Because it is just about the last digit.

you can visit: this site for the better explanation to find out last digit of a^b

Upvotes: 1

Related Questions