Tekrarlı rakam toplamı
Görev tanımı
Problem
Negatif olmayan bir tam sayı al ve ondalık basamaklarını topla. Sonuç birden fazla basamaklıysa onun basamaklarını yeniden topla ve tek bir basamak kalana kadar devam et. O basamağı döndür; ideal olarak hiç döngü kurmadan.
Örnekler
Input: n = 38
Output: 2
Neden: 3 + 8 = 11, sonra 1 + 1 = 2
Input: n = 99999
Output: 9
Neden: basamakların toplamı 45, 4 + 5 de 9
Input: n = 0
Output: 0
Neden: edge case: sıfır zaten tek basamak ve 0'da biten tek sayı
İpuçları
0 / 3
Süreci simüle etmek kolay. İlginç soru, son basamağın doğrudan sayıdan tahmin edilip edilemeyeceği.
On, dokuza bölündüğünde bir kalanını verir; onun her kuvveti de öyle. Bunun bir sayı ve basamaklarının toplamı hakkında ne söylediğini düşün.
Bir sayı ve basamak toplamı mod dokuza göre aynı kalanı verir; yani son basamağı n mod 9 belirler. Pozitif sayılar için sıfır kalanını 9'a eşle ve n'in 0'a eşit olduğu durumu ayrı ele al; 1 artı (n eksi 1) mod 9 ifadesi iki eşlemeyi birden yapar.
- Hedef zaman
- O(1)
- Hedef alan
- O(1)
Kısıtlar
- n ≥ 0
Çözüm
Onun her kuvveti dokuzun bir katından bir fazladır; bu yüzden bir sayı ile basamaklarının toplamı mod dokuza göre aynı kalanı verir ve bu kalan sürecin her turundan sağ çıkar. Bu yüzden son tek basamak, 1'den 9'a kadar n ile aynı kalanı veren tek basamaktır; yani 1 artı (n eksi 1) mod 9; 0'da biten tek sayı da sıfırdır. Döngüye gerek yok. Zaman ve alan O(1).
def digit_root(n):
if n == 0:
return 0 # the only number whose digits sum to 0
return 1 + (n - 1) % 9 # digit sums preserve the remainder mod 9
print(digit_root(38)) # -> 2
print(digit_root(99999)) # -> 9
print(digit_root(0)) # -> 0
print(digit_root(9)) # -> 9Kodda değil de fikirde mi takıldın? Modüler aritmetik bunu anlatıyor.