Sum of Digits

Q: Berapa kompleksitas waktu untuk menjumlahkan digit-digit sebuah bilangan?

Satu langkah untuk setiap digit, jadi O(d) , dengan d adalah jumlah digit. Sebuah bilangan n memiliki sekitar log10(n) + 1 digit, jadi batas yang sama sering ditulis sebagai O(log n) . Untuk bilangan bulat 32-bit, jumlahnya paling banyak 10 langkah.

Q: Mana yang lebih baik, versi string atau versi aritmetika?

Keduanya memiliki kompleksitas O(d) dan keduanya benar. Versi string lebih singkat dalam banyak bahasa, tetapi membuat salinan digit. Versi aritmetika menggunakan memori tambahan O(1) dan menunjukkan bahwa kamu memahami cara % 10 dan / 10 memisahkan angka, yang kembali berguna dalam soal palindrom dan pembalikan digit.

PemulaMatematika dan simulasi

+10

Kamu mendapatkan bilangan bulat nonnegatif n. Kembalikan jumlah digit desimalnya. Misalnya, digit dari 482 adalah 4, 8, dan 2, jadi jawabannya adalah 14.

Fungsi

sumOfDigits(n: integer) → integer

ninteger: bilangan bulat nonnegatif yang digit-digitnya kamu jumlahkan
Mengembalikaninteger: jumlah digit desimal dari n

Batasan

0 ≤ n ≤ 2³¹-1

Contoh

Input: n = 9045
Output: 18
Penjelasan: Digit dari 9045 adalah 9, 0, 4, dan 5, serta 9 + 0 + 4 + 5 = 18. Nol tidak menambahkan apa pun, tetapi tetap dihitung sebagai digit.

Input: n = 7
Output: 7
Penjelasan: Bilangan satu digit adalah jumlah digitnya sendiri, jadi 7 menghasilkan 7.

Petunjuk

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

0 dari 3 dibuka

Solusi

Pisahkan angka itu satu digit setiap kali. Kamu bisa membaca teks desimalnya, atau mengambil digit terakhir dengan n % 10 dan membuangnya dengan pembagian bilangan bulat dengan 10. Keduanya memerlukan satu langkah per digit, yang ditulis d, dan d ≤ 10 di sini. Versi aritmetika tidak memerlukan memori tambahan.

Baca digit sebagai teks

Intuisi

Ubah n menjadi teks desimalnya, sehingga 9045 menjadi karakter 9, 0, 4 dan 5, lalu jumlahkan nilai masing-masing karakter.

Karakter belum menjadi angka. Karakter '4' disimpan sebagai kode 52, jadi kamu perlu menguraikannya atau mengurangi kodenya dengan kode '0': '4' - '0' = 4. Karakter digit memiliki kode yang berurutan, sehingga pengurangan itu berlaku untuk kesepuluh digit.

Perulangan ini membutuhkan waktu O(d), dan teksnya membutuhkan ruang tambahan O(d).

Algoritma

Ubah n menjadi teks desimal.
Tetapkan total = 0.
Untuk setiap karakter, tambahkan nilai digitnya ke total.
Kembalikan total.

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

Ambil digit terakhir dengan % 10

Intuisi

Sisa pembagian dengan 10 adalah digit terakhir: 9045 % 10 = 5. Pembagian bilangan bulat dengan 10 membuang digit tersebut: 9045 / 10 = 904 jika bagian pecahannya dibuang. Ulangi pasangan operasi ini, maka digit-digitnya akan muncul dari kanan ke kiri.

Untuk 9045: tambahkan 5 dan simpan 904, tambahkan 4 dan simpan 90, tambahkan 0 dan simpan 9, tambahkan 9 dan simpan 0. Perulangan berhenti pada 0 dengan total 18. Untuk n = 0, perulangan tidak pernah berjalan dan jawabannya adalah 0.

Ada d langkah dan hanya dua bilangan bulat di memori: waktu O(d), ruang O(1). Setiap nilai perantara lebih kecil daripada n, jadi tidak ada yang bisa mengalami overflow.

Algoritma

Tetapkan total = 0.
Selama n > 0, tambahkan n % 10 ke total.
Bagilah n dengan 10, buang pecahannya.
Saat n mencapai 0, kembalikan total.

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

Jebakan dan kasus tepi

Menggunakan / saat bahasa pemrograman tersebut mengartikannya sebagai pembagian biasa. Dalam JavaScript, TypeScript, Lua, PHP, dan R, 9045 / 10 menghasilkan 904.5, dan perulangan menjumlahkan pecahan. Bulatkan ke bawah dengan Math.floor atau math.floor; dalam Python gunakan //, dalam Dart ~/, dalam PHP intdiv, dan dalam R %/%.
Menjumlahkan karakter, bukan digit. Karakter '7' memiliki kode 55, bukan 7.
Melakukan perulangan selama n >= 10. Digit pertama tetap berada di n dan tidak ikut dijumlahkan, sehingga 9045 menghasilkan 9, bukan 18.
Mengubah angka besar menjadi teks dalam R. as.character(100000) menghasilkan "1e+05"; gunakan format(n, scientific = FALSE).

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk menjumlahkan digit-digit sebuah bilangan?

Satu langkah untuk setiap digit, jadi O(d), dengan d adalah jumlah digit. Sebuah bilangan n memiliki sekitar log10(n) + 1 digit, jadi batas yang sama sering ditulis sebagai O(log n). Untuk bilangan bulat 32-bit, jumlahnya paling banyak 10 langkah.

Apa akar digital dari suatu angka?

Hasilnya didapat dengan menjumlahkan digit berulang kali sampai tersisa satu digit: 9045 menghasilkan 18, lalu 9. Untuk n positif, hasilnya sama dengan 1 + (n-1) % 9, karena setiap bilangan memiliki sisa pembagian 9 yang sama dengan jumlah digitnya.

Mana yang lebih baik, versi string atau versi aritmetika?

Keduanya memiliki kompleksitas O(d) dan keduanya benar. Versi string lebih singkat dalam banyak bahasa, tetapi membuat salinan digit. Versi aritmetika menggunakan memori tambahan O(1) dan menunjukkan bahwa kamu memahami cara % 10 dan / 10 memisahkan angka, yang kembali berguna dalam soal palindrom dan pembalikan digit.

def sumOfDigits(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 9045

Output yang diharapkan