Last digit of a large number(power) python

Question

Found this on Codewars. The function takes two arguments A and B and returns the last digit of A^B. The code below passes the first two test cases, but won't pass the next ones.

def last_digit(n1, n2):
    number = n1**n2
    if number % 2 == 0:
        return number % 10
    elif number % 2 != 0:
        return number % 10

Test.it("Example tests")
Test.assert_equals(last_digit(4, 1), 4)
Test.assert_equals(last_digit(4, 2), 6)
Test.assert_equals(last_digit(9, 7), 9)
Test.assert_equals(last_digit(10, 10 ** 10), 0)

Answer 1

Don't compute n1**n2. The problem comes when you attempt to compute:

10**(10**10)

That is a 1 followed by ten billion zeroes.

Use pow(n1, n2, 10) this makes the problem (more) tractable as it computes the exponentiation modulo 10. Then as the number is already reduced modulo 10 the function can be rewritten as:

def last_digit(n1, n2):
    return pow(n1, n2, 10)

Answer 2

Problem is easy to solve once you realize that the last digits of powers form a cycle. For example:

2: 2, 4, 8, 6, 2, 4
3: 3, 9, 7, 1, 3, 9

With that in mind you can create the cycle first and then just index it with modulo of n2:

def last_digit(n1, n2):
    if n2 == 0:
        return 1

    cycle = [n1 % 10]
    while True:
        nxt = (cycle[-1] * n1) % 10
        if nxt == cycle[0]:
            break
        cycle.append(nxt)
    return cycle[(n2 - 1) % len(cycle)]

This is also faster than using pow:

def last_digit_pow(n1, n2):
    return pow(n1, n2, 10)

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("last_digit(10, 10 ** 10)", setup="from __main__ import last_digit"))
    print(timeit.timeit("last_digit_pow(10, 10 ** 10)", setup="from __main__ import last_digit_pow"))

Output (Windows 8 & Python 2.7):

0.832171277335
4.08073167307

Output (Windows 8 & Python 3.5):

0.6951034093766606
1.9045515428013722

Output with 10**100 (Windows 8 & Python 3.5):

0.8367381690724996
10.928452962508006