Count Digits

Q: Berapa kompleksitas waktu untuk menghitung digit?

Sebuah bilangan n memiliki floor(log10(n)) + 1 digit, dan perulangan melakukan satu pembagian untuk setiap digit, sehingga berjalan dalam waktu O(log n) dan menggunakan ruang O(1) . Untuk bilangan bulat 32-bit, jumlahnya paling banyak 10 langkah.

Q: Bisakah kamu menggunakan log10 untuk menghitung jumlah digit suatu angka?

Untuk n positif, jumlahnya adalah floor(log10(n)) + 1 , tetapi logaritma dihitung dalam floating point. Nilainya tidak terdefinisi untuk 0, dan saat mendekati pangkat sepuluh, hasilnya bisa dibulatkan ke arah yang keliru: log10(10^15-1) menghasilkan tepat 15 dalam presisi double. Pembagian bilangan bulat selalu eksak.

PemulaMatematika dan simulasi

+10

Diberikan bilangan bulat non-negatif n, kembalikan jumlah digitnya jika ditulis dalam basis 10 tanpa nol di depan. Nol ditulis sebagai satu digit 0, jadi jumlah digitnya satu.

Fungsi

countDigits(n: integer) → integer

ninteger: bilangan bulat nonnegatif yang akan diukur
Mengembalikaninteger: jumlah digit desimal dalam n

Batasan

0 ≤ n ≤ 2³¹-1

Contoh

Input: n = 4096
Output: 4
Penjelasan: Pembagian bilangan bulat dengan 10 mengubah 4096 menjadi 409, 40, lalu 4: tiga digit dihilangkan dan satu tersisa, jadi jawabannya adalah 4.

Input: n = 0
Output: 1
Penjelasan: 0 ditulis dengan satu digit. Perulangan yang menghitung selama angkanya lebih besar dari 0 tidak pernah berjalan di sini dan mengembalikan 0, bukan 1.

Input: n = 100
Output: 3
Penjelasan: Nol juga termasuk digit: 100 ditulis sebagai 1, 0, 0, jadi jawabannya adalah 3.

Pertanyaan lanjutan

Bisakah kamu menghitung digit tanpa perulangan yang berjalan satu kali untuk setiap digit, misalnya dengan pencarian biner pada pangkat sepuluh?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap pembagian bilangan bulat dengan 10 menghilangkan satu digit. Hitung pembagiannya sampai tersisa satu digit, lalu tambahkan satu untuk digit tersebut. Bug muncul di kasus-kasus tepi: 0 memiliki satu digit, dan rumus logaritma gagal pada 0 serta pada angka yang sedikit lebih kecil daripada pangkat sepuluh yang besar.

Tuliskan angka sebagai teks dan hitung karakternya

Intuisi

Bahasamu sudah menulis n dalam desimal. Minta string tersebut dan hitung karakternya: 4096 menjadi "4096", empat karakter, dan 0 menjadi "0", jadi nol tidak memerlukan penanganan khusus.

Konversi ini melakukan satu pembagian untuk setiap digit, sehingga waktu dan memori tambahan sama-sama O(log n), paling banyak 10 karakter di sini.

Algoritma

Ubah n menjadi string desimal dengan fungsi yang tidak pernah beralih ke notasi ilmiah.
Hitung jumlah karakter dalam string tersebut.
Kembalikan jumlah itu. Untuk 0, string-nya adalah "0", jadi jawabannya 1 tanpa pemeriksaan tambahan.

def countDigits(n):
    return len(str(n))

Bagi dengan 10 sampai tersisa satu digit

Intuisi

Mulai hitungan dari 1 dan bagi dengan 10 selama n ≥ 10, lalu tambahkan 1 setiap kali pembagian. Memulai dari 1 menunjukkan bahwa setiap angka memiliki setidaknya satu digit, tepat seperti aturan untuk 0, jadi pemeriksaan terpisah tidak diperlukan.

Perulangan berjalan paling banyak 9 kali untuk 2147483647: waktu O(log n). Perulangan ini menyimpan satu pencacah dan mengubah salinan n miliknya sendiri, jadi ruang tambahan adalah O(1).

Algoritma

Tetapkan count = 1 untuk digit yang selalu ada.
Selama n ≥ 10, bagi n dengan 10 menggunakan pembagian bilangan bulat, lalu tambahkan 1 ke count.
Ketika tersisa satu digit, kembalikan count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

Jebakan dan kasus tepi

Menghitung mulai dari 0 selama n > 0. Hasilnya 0 untuk n = 0.
Menggunakan floor(log10(n)) + 1. Cara ini gagal untuk 0, karena logaritmanya adalah minus tak hingga, dan untuk 10^15-1, karena presisi ganda membulatkan logaritma menjadi tepat 15 sehingga rumusnya menghasilkan 16 digit.
Pembagian riil di JavaScript, Lua, PHP, atau R, yang membuat / mempertahankan pecahan. Perulangan selama n > 0 kemudian berjalan 328 kali untuk 4096. Gunakan Math.floor, math.floor, intdiv, atau %/%.
Notasi ilmiah pada versi string. R menulis as.character(1e5) sebagai "1e+05"; gunakan sprintf("%.0f", n). Di Lua 5.3 dan versi setelahnya, tostring(4096.0) mempertahankan .0; gunakan string.format("%d", n).

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk menghitung digit?

Sebuah bilangan n memiliki floor(log10(n)) + 1 digit, dan perulangan melakukan satu pembagian untuk setiap digit, sehingga berjalan dalam waktu O(log n) dan menggunakan ruang O(1). Untuk bilangan bulat 32-bit, jumlahnya paling banyak 10 langkah.

Bisakah kamu menggunakan log10 untuk menghitung jumlah digit suatu angka?

Untuk n positif, jumlahnya adalah floor(log10(n)) + 1, tetapi logaritma dihitung dalam floating point. Nilainya tidak terdefinisi untuk 0, dan saat mendekati pangkat sepuluh, hasilnya bisa dibulatkan ke arah yang keliru: log10(10^15-1) menghasilkan tepat 15 dalam presisi double. Pembagian bilangan bulat selalu eksak.

Bagaimana cara menghitung jumlah digit bilangan negatif?

Ambil nilai absolut terlebih dahulu, lalu hitung seperti biasa. String(-42) memiliki tiga karakter karena tanda minus bukan digit. Untuk bilangan bulat 32-bit terkecil, ambil nilai absolut dalam tipe 64-bit karena nilainya tidak muat dalam 32 bit.

def countDigits(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 4096

Output yang diharapkan