Dernier chiffre d'un grand nombre (puissance) python

Question

Trouvé sur Codewars. Il suppose de prendre deux nombres a et b et renvoie le dernier chiffre décimal de a^b. Les deux premiers cas de test passent mais le suivant ne va pas.

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

Ne pas calculer n1**n2. Le problème vient quand vous essayez de calculer:

10**(10**10) 

C'est un 1 suivi de dix milliards de zéros.

Utilisez pow(n1, n2, 10) cela rend le problème (plus) traitable car il calcule le module d'exponentiation 10. Alors que le nombre est déjà réduit modulo 10 la fonction peut être réécrite comme:

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

Answer 2

problème est facile à résoudre une fois que vous réalisez que les derniers chiffres des puissances forment un cycle. Par exemple:

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

Dans cet esprit, vous pouvez créer le premier cycle et puis juste indexer avec modulo 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)] 

Ceci est également plus rapide que d'utiliser 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")) 

Sortie (Windows 8 & Python 2.7):

0.832171277335 
4.08073167307 

Sortie (Windows 8 & Python 3.5):

0.6951034093766606 
1.9045515428013722 

sortie avec 10**100 (Windows 8 & Python 3.5):

0.8367381690724996 
10.928452962508006