Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Last digit of a large number(power) python

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)
like image 934
Eggiderm Avatar asked Dec 10 '16 02:12

Eggiderm


People also ask

How do you find the last digit of a number to a large power?

In general, the last digit of a power in base n n n is its remainder upon division by n n n.

How do I get the last digit of a number in Python?

To find last digit of a number, we use modulo operator %. When modulo divided by 10 returns its last digit.


2 Answers

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)
like image 94
Dan D. Avatar answered Oct 25 '22 09:10

Dan D.


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
like image 20
niemmi Avatar answered Oct 25 '22 11:10

niemmi