CODEWITHSUNDEEP
pythonpython-3.x
Eggiderm
Eggiderm

Reputation: 87

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)

Upvotes: 7

Views: 8631

Answers (3)

baduker
baduker

Reputation: 20042

I know this post is old, but maybe someone will find this dictionary-based approach useful, too.

cycles = {
    0: [0,0,0,0],   
    1: [1,1,1,1],
    2: [2,4,8,6],
    3: [3,9,7,1],
    4: [4,6,4,6], 
    5: [5,5,5,5], 
    6: [6,6,6,6], 
    7: [7,9,3,1], 
    8: [8,4,2,6], 
    9: [9,1,9,1], 
}

def last_digit(n1, n2):
    if n2 == 0:
        return 1
    else:
        n1_last_digit = int(str(n1)[-1])
        cycle = cycles[n1_last_digit]
        return cycle[(n2 % 4) - 1]

Upvotes: 3

niemmi
niemmi

Reputation: 17263

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

Upvotes: 8

Dan D.
Dan D.

Reputation: 74645

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)

Upvotes: 10

Related Questions