Count Digits
Negatif olmayan bir tamsayı n verildiğinde, baştaki sıfırlar olmadan 10 tabanında yazıldığında kaç basamağı olduğunu döndürün. Sıfır tek bir 0 olarak yazılır, bu nedenle bir basamağı vardır.
Fonksiyon
- ninteger
- ölçülecek negatif olmayan tam sayı
- Döndürürinteger
- n'deki ondalık basamak sayısı
Kısıtlar
0 ≤ n ≤ 231-1
Örnekler
- Girdi
- n = 4096
- Çıktı
- 4
- Açıklama
- 10'a tam sayı bölme,
4096sayısını409,40ve4sayılarına dönüştürür: üç basamak çıkarılır ve bir basamak kalır, bu nedenle cevap4'tür.
- Girdi
- n = 0
- Çıktı
- 1
- Açıklama
0tek basamakla yazılır. Sayı 0'dan büyük olduğu sürece sayan bir döngü burada hiç çalışmaz ve1yerine0döndürür.
- Girdi
- n = 100
- Çıktı
- 3
- Açıklama
- Sıfırlar da birer basamaktır:
100,1,0,0şeklinde yazılır, bu yüzden cevap3'tür.
Ek soru
Örneğin, 10'un kuvvetleri üzerinde ikili arama yaparak her basamak için bir kez çalışan bir döngü olmadan basamakları sayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir sayıyı 10'a bölüp kalanı attığınızda basamak sayısına ne olur?
10'a yapılan her tam sayı bölmesi sondan tam olarak bir basamağı siler. Tek basamaklı bir sayıya ulaşmak için kaç bölme gerektiğini say.
Bir sayacı 1'den başlat ve sayı en az 10 olduğu sürece 10'a bölüp her seferinde 1 ekle. 1'den başlamak
0için de doğru yanıtı verir.
Çözüm
10'a yapılan her tam sayı bölme bir basamağı kaldırır. Bir basamak kalana kadar bölmeleri say, ardından o basamak için bir ekle. Hatalar uç durumlarda ortaya çıkar: 0 bir basamaklıdır ve logaritma formülü 0 için ve büyük 10 kuvvetlerinin biraz altındaki değerlerde başarısız olur.
Sayıyı metin olarak yazın ve karakterleri sayın
Sezgi
Diliniz n sayısını zaten ondalık olarak yazar. Bu dizgiyi isteyin ve karakterlerini sayın: 4096, dört karakterli "4096" olur ve 0, "0" olur; dolayısıyla sıfır için özel bir durum gerekmez.
Dönüştürme, her basamak için bir bölme işlemi yapar; bu nedenle hem zaman hem de ek bellek O(log n) olur, burada en fazla 10 karakter vardır.
Algoritma
ndeğerini bilimsel gösterime asla geçmeyen bir işlevle ondalık dizgeye dönüştür.- Dizgedeki karakterleri say.
- Bu sayıyı döndür.
0için dizge"0"olur, bu nedenle ek bir kontrol yapmadan yanıt1olur.
def countDigits(n):
return len(str(n))Tek basamak kalana kadar 10'a böl
Sezgi
Sayımı 1'den başlatın ve n ≥ 10 olduğu sürece 10'a bölerek her bölme için 1 ekleyin. 1'den başlamak, her sayının en az bir basamağı olduğunu belirtir; bu da 0 için geçerli olan kuralın ta kendisidir, dolayısıyla ayrı bir kontrol gerekmez.
Döngü, 2147483647 için en fazla 9 kez çalışır: O(log n) zaman. Tek bir sayaç tutar ve n'nin kendi kopyasını değiştirir; bu nedenle ek alan O(1)'dir.
Algoritma
- Her zaman bulunan basamak için
count = 1olarak ayarla. n ≥ 10olduğu sürecen'yi tam sayı bölmesiyle 10'a böl vecount'a 1 ekle.- Bir basamak kaldığında
count'u döndür.
def countDigits(n):
count = 1 # every number, 0 included, has at least one digit
while n >= 10:
n //= 10
count += 1
return count
Tuzaklar ve uç durumlar
n > 0koşuluyla 0'dan başlayarak sayma.n = 0için0döndürür.floor(log10(n)) + 1kullanma. Logaritmanın eksi sonsuz olduğu0için ve çift duyarlığın logaritmayı tam olarak 15'e yuvarladığı, formülün de 16 basamak verdiği10^15-1için başarısız olur./işlecinin kesirli kısmı koruduğu JavaScript, Lua, PHP veya R'de gerçek bölme. Ardındann > 0koşuluyla çalışan bir döngü,4096için 328 kez döner.Math.floor,math.floor,intdivveya%/%kullan.- String sürümünde bilimsel gösterim. R,
as.character(1e5)değerini"1e+05"olarak yazar;sprintf("%.0f", n)kullan. Lua 5.3 ve sonraki sürümlerdetostring(4096.0),.0kısmını korur;string.format("%d", n)kullan.
Sıkça sorulan sorular3
Basamakları saymanın zaman karmaşıklığı nedir?
Bir n sayısının floor(log10(n)) + 1 basamağı vardır ve döngü her basamak için bir bölme işlemi yapar; bu nedenle O(log n) zamanda ve O(1) alanda çalışır. 32 bitlik bir tam sayı için bu, en fazla 10 adımdır.
Bir sayının basamak sayısını bulmak için log10 kullanabilir misin?
Pozitif bir n için sayı floor(log10(n)) + 1 olur, ancak logaritma kayan noktalı sayılarla hesaplanır. 0 için tanımsızdır ve 10'un bir kuvvetine yakın değerlerde yanlış yönde yuvarlanabilir: log10(10^15-1), double precision'da tam olarak 15 sonucunu verir. Tamsayı bölmesi her zaman kesindir.
Negatif bir sayının rakamlarını nasıl sayarsınız?
Önce mutlak değeri al, ardından her zamanki gibi say. String(-42) üç karakterden oluşur çünkü eksi işareti bir rakam değildir. En küçük 32 bitlik tam sayı için mutlak değeri 64 bitlik bir türde al; çünkü 32 bite sığmaz.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def countDigits(n):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
n = 4096
Beklenen Çıktı
4