Sum of Digits

Q: Sayı basamaklarını toplamanın zaman karmaşıklığı nedir?

Her basamak için bir adım, yani O(d) ; burada d , basamak sayısıdır. Bir n sayısının yaklaşık log10(n) + 1 basamağı vardır, bu nedenle aynı sınır genellikle O(log n) olarak yazılır. 32 bitlik bir tamsayı için bu, en fazla 10 adımdır.

Q: Bir sayıyı dizgeye dönüştürmeden basamaklarını nasıl elde edersiniz?

Kalanı ve 10'a tam sayı bölme işlemini kullanın. n % 10 son basamaktır ve n 'yi kalanını atarak 10'a bölmek bu basamağı kaldırır. n 0'a ulaşana kadar tekrarlayın; böylece sağdan sola her basamağı ziyaret edersiniz.

Q: String sürümü mü yoksa aritmetik sürümü mü daha iyi?

Her ikisi de O(d) karmaşıklığındadır ve ikisi de doğrudur. Dize sürümünü birçok dilde yazmak daha kısadır, ancak rakamların bir kopyasını oluşturur. Aritmetik sürüm, O(1) ek bellek kullanır ve görüşmeciye % 10 ile / 10 işlemlerinin bir sayıyı nasıl parçalara ayırdığını bildiğini gösterir; bu bilgi palindrom ve rakamları ters çevirme problemlerinde yeniden karşına çıkar.

BaşlangıçMatematik ve simülasyon

+10

Negatif olmayan bir tam sayı n alırsın. Ondalık basamaklarının toplamını döndür. Örneğin, 482 sayısının basamakları 4, 8 ve 2'dir; dolayısıyla cevap 14 olur.

Fonksiyon

sumOfDigits(n: integer) → integer

ninteger: rakamlarını topladığınız negatif olmayan tam sayı
Döndürürinteger: n'nin ondalık basamaklarının toplamı

Kısıtlar

0 ≤ n ≤ 2³¹-1

Örnekler

Girdi: n = 9045
Çıktı: 18
Açıklama: 9045 sayısının basamakları 9, 0, 4 ve 5'tir ve 9 + 0 + 4 + 5 = 18. Sıfır hiçbir şey eklemez ama yine de bir basamak olarak sayılır.

Girdi: n = 7
Çıktı: 7
Açıklama: Tek basamaklı bir sayı, kendi rakamları toplamına eşittir; dolayısıyla 7, 7 sonucunu verir.

Gönderirken +15 gizli test

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir sayı rakamlarını sana tek tek vermez; onu parçalarına ayırman gerekir. Onu metne dönüştürüp karakterleri okuyabilir ya da son rakamı ayıklayan iki aritmetik işlemi kullanabilirsin: n % 10 bu rakamı verir, 10 ile tam sayı bölmesi ise onu kaldırır. Her ikisi de aşağıda d ile gösterilen, rakam başına bir adım alır ve burada d ≤ 10. Aritmetik yöntem ek bellek gerektirmez.

Rakamları metin olarak okuyun

Sezgi

Bir sayıyı yazdığında, rakamlarını zaten görürsün. n'yi ondalık metne dönüştür; 9045, 9, 0, 4 ve 5 olmak üzere dört karaktere dönüşür; ardından karakterlerin üzerinden geçip her birinin değerini ekle.

Bir karakter henüz sayı değildir. '4' karakteri 52 koduyla saklanır; bu yüzden onu ayrıştırabilir veya '0' kodunu çıkarabilirsin: '4' - '0' = 4. Rakam karakterlerinin kodları ardışık olduğundan, bu çıkarma işlemi on karakterin tümü için çalışır.

Metin, her rakam için bir tane olmak üzere d karakter içerir; bu nedenle döngü O(d) zaman alır ve metnin kendisi O(d) ek alan kullanır.

Algoritma

n'yi ondalık metne dönüştür.
total = 0 olarak ayarla.
Her karakter için, basamak değerini total'a ekle.
total'ı döndür.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Son basamağı % 10 ile ayırın

Sezgi

Bir sayıyı metin kullanmadan basamaklarına ayırabilirsin. Bir sayının 10'a bölümünden kalan son basamağı verir: 9045 % 10 = 5. 10'a tam sayı bölümü bu basamağı atar: kesir kısmı atıldığında 9045 / 10 = 904. Bu ikili işlemi tekrarladığında basamaklar sağdan sola çıkar.

9045 için: 5'i ekle ve 904'ü tut, 4'ü ekle ve 90'ı tut, 0'ı ekle ve 9'u tut, 9'u ekle ve 0'ı tut. Döngü 0'da durur ve toplam 18 olur. n = 0 için döngü hiç çalışmaz ve yanıt 0 olur; bu doğrudur.

Her adım bir basamağı kaldırır; dolayısıyla d adım, O(d) zaman ve bellekte yalnızca iki tam sayı bulunur; alan kullanımı O(1)'dir. Ara değerlerin her biri n'den küçüktür, bu yüzden taşma meydana gelemez.

Algoritma

total = 0 olarak ayarla.
n > 0 olduğu sürece n % 10 değerini total'a ekle.
n'i 10'a böl ve kesir kısmını at.
n 0'a ulaştığında total değerini döndür.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Tuzaklar ve uç durumlar

Döngü kısadır; hatalar türlerle ve en küçük girdiyle ilgilidir.

Dilin gerçek bölme anlamında kullandığı yerde / kullanmak. JavaScript, TypeScript, Lua, PHP ve R dillerinde 9045 / 10, 904.5 sonucunu verir ve döngü bu durumda kesirler ekler. Aşağı yuvarlamak için Math.floor veya math.floor kullanın; Python'da //, Dart'ta ~/, PHP'de intdiv, R'de %/% kullanın.
Rakamlar yerine karakterleri eklemek. '7' karakterinin kodu 7 değil, 55'tir. '0' çıkarın veya önce karakteri ayrıştırın.
n >= 10 koşuluyla döngü kurmak. Bu durumda döngü, baştaki rakam hâlâ n içindeyken durur ve bu rakamı hiç eklemez; dolayısıyla 9045, 18 yerine 9 sonucunu verir. n > 0 koşuluyla döngü kurun; bu, n = 0 için de 0 döndürür.
R'de büyük sayıları metin olarak yazdırmak. as.character(100000), sayının altı basamağını değil, "1e+05" sonucunu verir. format(n, scientific = FALSE) kullanın.

Sıkça sorulan sorular4

Sayı basamaklarını toplamanın zaman karmaşıklığı nedir?

Her basamak için bir adım, yani O(d); burada d, basamak sayısıdır. Bir n sayısının yaklaşık log10(n) + 1 basamağı vardır, bu nedenle aynı sınır genellikle O(log n) olarak yazılır. 32 bitlik bir tamsayı için bu, en fazla 10 adımdır.

Bir sayıyı dizgeye dönüştürmeden basamaklarını nasıl elde edersiniz?

Kalanı ve 10'a tam sayı bölme işlemini kullanın. n % 10 son basamaktır ve n'yi kalanını atarak 10'a bölmek bu basamağı kaldırır. n 0'a ulaşana kadar tekrarlayın; böylece sağdan sola her basamağı ziyaret edersiniz.

Bir sayının dijital kökü nedir?

Rakamları, tek bir rakam kalana kadar tekrar tekrar toplayarak elde edilir: 9045 önce 18, sonra 9 verir. Pozitif bir n için değeri 1 + (n-1) % 9 olur; çünkü her sayı 9'a bölündüğünde, rakamları toplamıyla aynı kalanı verir.

String sürümü mü yoksa aritmetik sürümü mü daha iyi?

Her ikisi de O(d) karmaşıklığındadır ve ikisi de doğrudur. Dize sürümünü birçok dilde yazmak daha kısadır, ancak rakamların bir kopyasını oluşturur. Aritmetik sürüm, O(1) ek bellek kullanır ve görüşmeciye % 10 ile / 10 işlemlerinin bir sayıyı nasıl parçalara ayırdığını bildiğini gösterir; bu bilgi palindrom ve rakamları ters çevirme problemlerinde yeniden karşına çıkar.

Python

def sumOfDigits(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

n = 9045

Beklenen