Count Digits
Negatif olmayan bir n tam sayısı alan ve bu sayı baştaki sıfırlar olmadan 10 tabanında yazıldığında kaç basamağı olduğunu döndüren bir fonksiyon yazın. Sıfır tek bir 0 olarak yazılır, dolayısıyla 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,40ve4değerlerine dönüştürür. Bu, üç basamağın çıkarılıp bir basamağın kalması demektir; dolayısıyla 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 basamaktır:
100,1,0,0olarak yazılır; bu nedenle cevap3'tür.
Gönderirken +16 gizli test
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 bölme işlemi, sondan tam olarak bir basamağı kaldırır. Tek basamaklı bir sayıya ulaşmanın kaç bölme işlemi sürdüğünü sayın.
Bir sayacı 1'den başlat ve sayı en az 10 olduğu sürece 10'a bölerek her seferinde 1 ekle. 1'den başlamak,
0için de doğru yanıtı verir.
Çözüm
Basamak sayısı, geriye tek bir basamak kalana kadar 10'a kaç kez bölebileceğinizin sayısına, o basamak da eklenerek bulunur. Fikir tek satıra sığar; asıl iş sınır durumlarındadır. 0 tek basamaklıdır, sayı 9 ile 10 arasında değişir ve logaritma tabanlı bir formül 0 için, kayan noktalı aritmetikte ise büyük on kuvvetlerinin biraz altında hata verir.
Sayıyı metin olarak yazın ve karakterleri sayın
Sezgi
Dilin ondalık biçimde n yazmayı zaten biliyor. Ondan bu dizgeyi iste ve karakterleri say: 4096, dört karakterli "4096" olur. 0, tek karakterli "0" olur; dolayısıyla sıfır için özel durum gerekmez.
Dönüştürme, kütüphane içinde her basamak için bir kez 10'a böler; bu nedenle işlem miktarı O(log n) olur. Dizge her basamak için bir karakter tutar; bu da O(log n) ek bellek demektir ve burada en fazla 10 karakter kullanılır.
Biçimlendirme düz ondalık olmalıdır. R'de as.character(1e5), altı basamaklı bir sayı için beş karakter olan "1e+05" sonucunu verir; bu yüzden sprintf("%.0f", n) ile biçimlendirin. Lua 5.3 ve sonrasında tostring(4096.0), .0 kısmını korurken string.format("%d", n) her sürümde tamsayıyı yazar.
Algoritma
n'yi bilimsel gösterime hiçbir zaman geçmeyen bir işlevle ondalık dizgesine dönüştür.- Dizgedeki karakterleri say.
- Bu sayıyı döndür.
0için dize"0"olduğundan, ek bir kontrol yapmadan yanıt1'dir.
def countDigits(n):
return len(str(n))Tek basamak kalana kadar 10'a böl
Sezgi
10’a tam sayı bölme son basamağı kaldırır: 4096 / 10, 409 eder. Her bölme bir basamağı kaldırır; dolayısıyla tek basamağa ulaşmak için gereken bölme sayısına, son basamak için 1 eklenmesiyle cevap bulunur. 4096 için üç bölme gerekir (409, 40, 4), yani 4 basamağı vardır.
Sayacı 1’den başlat ve n ≥ 10 olduğu sürece böl. 1’den başlamak, her sayının en az bir basamağı olduğunu belirtir; bu da tam olarak 0 için geçerli kuraldır. Önce yazılan sürüm, 0’dan başlayıp n > 0 koşuluyla sayar ve n = 0 için 0 döndürür; ayrıca bir denetim gerektirir.
Döngü, ilk basamaktan sonraki her basamak için bir kez çalışır; 2147483647 için en fazla 9 kez çalışır, dolayısıyla O(log n) zaman alır. Bir sayaç tutar ve n’nin kendi kopyasını değiştirir; bu da O(1) ek alan demektir.
Algoritma
- Her zaman bulunan basamak için
count = 1değerini ayarla. n ≥ 10olduğu sürece,nsayısını tam sayı bölmesiyle 10'a böl vecountdeğerini 1 artır.- Bir basamak kaldığında
countdeğerini 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
Bu problemdeki her hata bir sınır durumunda ortaya çıkar.
n > 0koşulu sağlandığı sürece 0'dan başlayarak saymak. Bu, tüm pozitif sayılar için doğrudur ven = 0için0döndürür.floor(log10(n)) + 1kullanmak. Logaritmanın eksi sonsuz olduğu0değerinde ve 10'un kuvvetinin biraz altındaki büyük değerlerde başarısız olur: çift duyarlıktalog10(10^15-1)tam olarak15değerine yuvarlanır, dolayısıyla formül 15 yerine 16 basamak olduğunu söyler.n > 0koşulu sağlandığı sürece çalışan bir döngüde gerçek bölme kullanmak. JavaScript, Lua, PHP ve R'de/kesirli kısmı korur; bu nedenle4096, 0'a ulaşmadan önce 328 adım boyunca küçülerek 0'a yaklaşır.Math.floor,math.floor,intdivveya%/%kullanın.- Dize sürümünde bilimsel gösterim kullanmak: R,
100000değerini"1e+05"olarak yazar. - Eksi işaretini basamak olarak saymak. Buradaki girdi hiçbir zaman negatif değildir, ancak
String(-42)üç karakter içerir; bu nedenle negatif sayılar için kullanılan bir sürüm önce mutlak değeri alır.
Sıkça sorulan sorular4
Bir sayıyı dizgeye dönüştürmeden basamaklarını nasıl sayarsınız?
Tek bir basamak kalana kadar tam sayı bölmesiyle 10'a bölerek bölme işlemlerini say ve son basamak için 1 ekle. 4096, 409, 40, 4 olur: üç bölme işlemi, yani 4 basamak. Döngü O(1) ek alan kullanır.
0 neden bir basamağa sahip?
Sıfır, tek karakter olan 0 ile yazılır; bu nedenle onluk gösterimi bir basamaktan oluşur. Sayı 0'dan büyük olduğu sürece bölme işlemlerini sayan kod, 0 için hiç çalışmaz ve 0 döndürür. Sayacı 1'den başlatıp sayı en az 10 olduğu sürece bölmek, özel bir durum gerektirmeden bunu halleder.
Bir sayının basamak sayısını bulmak için log10 kullanabilir misin?
Bir pozitif n için basamak sayısı floor(log10(n)) + 1 olur, ancak logaritma kayan noktalı sayılarla hesaplanır. 0 için tanımsızdır ve 10'un kuvvetine yakın değerlerde yanlış yuvarlanabilir: log10(10^15-1), çift duyarlıkta tam olarak 15 sonucunu verir. Tamsayı bölmesi her seferinde kesin sonucu verir.
Basamakları saymanın zaman karmaşıklığı nedir?
Bir n sayısı floor(log10(n)) + 1 basamağa sahiptir ve döngü her basamak için bir bölme işlemi yaptığı için O(log n) zamanda çalışır. 32 bitlik bir tam sayı için bu en fazla 10 adımdır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def countDigits(n):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
n = 4096
Beklenen
4