Armstrong Number

Q: Berapa kompleksitas waktu untuk memeriksa bilangan Armstrong?

n memiliki sekitar log n digit, paling banyak 10 di sini. Mengambil digit satu per satu dan mencari setiap pangkatnya di tabel berisi sepuluh nilai membutuhkan waktu O(log n) dan ruang O(1) . Menghitung ulang d^k dengan perulangan untuk setiap digit membuatnya menjadi O(log² n) .

PemulaMatematika dan simulasi

+10

Bilangan bulat positif disebut bilangan Armstrong jika nilainya sama dengan jumlah setiap digitnya yang masing-masing dipangkatkan dengan jumlah digit bilangan tersebut. 153 memiliki tiga digit dan 1^3 + 5^3 + 3^3 = 153, jadi bilangan itu termasuk bilangan Armstrong. Tulis fungsi yang menerima n dan mengembalikan true jika bilangan tersebut adalah bilangan Armstrong dan false jika tidak.

Fungsi

isArmstrong(n: integer) → boolean

ninteger: bilangan bulat positif yang akan diuji
Mengembalikanboolean: benar ketika n sama dengan jumlah digit-digitnya, masing-masing dipangkatkan dengan jumlah digit

Batasan

1 ≤ n ≤ 10⁹

Contoh

Input: n = 153
Output: true
Penjelasan: 153 memiliki 3 digit, jadi setiap digit dipangkatkan tiga: 1 + 125 + 27 = 153. Jumlahnya menghasilkan kembali angka tersebut, jadi jawabannya adalah true.

Input: n = 10
Output: false
Penjelasan: 10 memiliki 2 digit, jadi setiap digit dikuadratkan: 1 + 0 = 1, yang bukan 10. Jawabannya adalah false.

Input: n = 9474
Output: true
Penjelasan: Dengan 4 digit, pangkatnya adalah 4: 6561 + 256 + 2401 + 256 = 9474, sama dengan angkanya sendiri, jadi jawabannya adalah true.

Pertanyaan lanjutan

Hanya ada 31 bilangan Armstrong antara 1 dan 10^9. Bisakah kamu mencantumkan semuanya tanpa menguji satu per satu satu miliar bilangan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Definisinya adalah algoritmanya: hitung digit-digit n, pangkatkan setiap digit dengan pangkat tersebut, jumlahkan hasilnya, lalu bandingkan dengan n. Eksponennya adalah jumlah digit n ini, bukan 3 yang tetap, dan jumlahnya dapat melampaui 32 bit: 999999999 menghasilkan 9 × 9^9 = 3486784401.

Baca digit dari string

Intuisi

String desimal dari n memberikan kedua hal yang kamu perlukan: panjangnya adalah eksponen k, dan karakter-karakternya adalah digit. Untuk 9474, kamu menjumlahkan 9^4 + 4^4 + 7^4 + 4^4. n adalah bilangan Armstrong tepat ketika totalnya sama dengan n.

Pangkat yang dihitung dengan k perkalian memerlukan k langkah per digit, jadi pemeriksaannya adalah O(k²) dengan k sekitar log n: paling banyak 100 perkalian di sini.

Algoritma

Ubah n menjadi string desimal dan tetapkan k sebagai panjangnya.
Tetapkan total 64-bit ke 0.
Untuk setiap karakter, ubah menjadi digit d dan tambahkan d^k ke total, dengan mengalikan bilangan bulat, bukan memanggil fungsi pangkat floating point.
Kembalikan apakah total sama dengan n.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Kupas digit dan cari nilai pangkatnya

Intuisi

Aritmetika melakukan hal yang sama tanpa string. m % 10 adalah digit terakhir dari m, dan pembagian bilangan bulat dengan 10 menghilangkannya, jadi pembagian berulang hingga tidak ada yang tersisa akan menghitung jumlah digit: 9474 menjadi 947, 94, 9, 0, jadi k = 4.

Hanya ada sepuluh digit, jadi buat powers[d] = d^k untuk d dari 0 hingga 9 terlebih dahulu. Dengan begitu, setiap digit hanya memerlukan satu pencarian, bukan k perkalian: waktu O(log n) dan ruang O(1).

Setiap suku bernilai nol atau positif, jadi setelah totalnya melebihi n, jawabannya adalah false. Untuk 999999999, itu terjadi setelah tiga digit, saat 3 × 387420489 = 1162261467.

Algoritma

Hitung digit n dengan membagi salinannya dengan 10 sampai nilainya mencapai 0. Sebut jumlahnya k.
Isi powers[d] = d^k untuk setiap digit d dari 0 hingga 9, menggunakan integer 64-bit.
Bagi salinan baru n dengan 10 lagi, lalu tambahkan powers[m % 10] ke total pada setiap langkah.
Jika total melebihi n, langsung kembalikan false.
Setelah digit terakhir, kembalikan apakah total sama dengan n.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

Jebakan dan kasus tepi

Pangkat tetap 3. Ini menerima 153 dan 370, tetapi menolak 9474 dan setiap bilangan satu digit di atas 1, karena 7^3 = 343.
Jumlah 32-bit. 999999999 menghasilkan jumlah 3486784401, dan untuk n = 10^9, entri tabel 9^10 adalah bilangan yang sama. C mengalami overflow yang menyebabkan perilaku tidak terdefinisi, Java dan C# membungkus nilainya menjadi bilangan negatif, sedangkan build debug Rust mengalami panic.
Pangkat bilangan titik mengambang. Beberapa runtime C menghasilkan 24.999... untuk pow(5, 2), lalu cast memotongnya menjadi 24. Kalikan bilangan bulat saja.
Membandingkan dengan nilai yang salah. Perulangan digit membagi n hingga menjadi 0, jadi gunakan salinannya.
Notasi ilmiah di R. as.character(1e9) menghasilkan "1e+09", yang terdiri dari lima karakter. Format dengan sprintf("%.0f", n).

Pertanyaan yang sering diajukan3

Apa itu bilangan Armstrong?

Bilangan Armstrong, yang juga disebut bilangan narsistik, sama dengan jumlah setiap digitnya yang masing-masing dipangkatkan dengan banyaknya digit. 9474 termasuk bilangan Armstrong karena 9^4 + 4^4 + 7^4 + 4^4 = 9474. Semua bilangan satu digit memenuhi syarat, karena d^1 = d.

Berapa banyak bilangan Armstrong yang ada?

Dalam basis 10, tepat ada 88 bilangan positif seperti ini, dan yang terbesar memiliki 39 digit. Daftarnya berhingga karena bilangan dengan k digit bernilai setidaknya 10^(k-1), sedangkan jumlah pangkat digitnya paling banyak k × 9^k, dan mulai dari 61 digit, jumlah tersebut tidak bisa menyusul.

Berapa kompleksitas waktu untuk memeriksa bilangan Armstrong?

n memiliki sekitar log n digit, paling banyak 10 di sini. Mengambil digit satu per satu dan mencari setiap pangkatnya di tabel berisi sepuluh nilai membutuhkan waktu O(log n) dan ruang O(1). Menghitung ulang d^k dengan perulangan untuk setiap digit membuatnya menjadi O(log² n).

def isArmstrong(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 153

Output yang diharapkan

true