Palindrome Number

Q: Apakah bilangan negatif merupakan palindrom?

Tidak. Jika dibaca dari belakang, -121 menjadi 121- , dan tanda minus tidak memiliki karakter yang cocok di ujung lainnya. Jadi, setiap bilangan bulat negatif mengembalikan false .

Q: Berapa kompleksitas waktu dari Palindrome Number?

Kedua pendekatan berjalan dalam waktu O(log x) , karena angka x memiliki sekitar log10(x) digit dan setiap digit diproses satu kali. Pendekatan string menggunakan ruang tambahan O(log x) untuk teks, sedangkan pembalikan setengah angka menggunakan O(1) .

MudahMatematika dan simulasi

+10

Sebuah angka disebut palindrom jika digit-digitnya dibaca sama dari kiri ke kanan maupun dari kanan ke kiri, seperti 1221. Diberikan bilangan bulat x, kembalikan true jika angka tersebut adalah palindrom dan false jika tidak. Angka negatif tidak pernah dihitung, karena tanda minusnya tidak memiliki pasangan di ujung lainnya.

Fungsi

isPalindrome(x: integer) → boolean

xinteger: bilangan bulat yang akan diperiksa, mungkin negatif
Mengembalikanboolean: true jika x terbaca sama dari kedua arah, false jika tidak

Batasan

-2³¹ ≤ x ≤ 2³¹-1
Setiap bilangan negatif menghasilkan false.

Contoh

Input: x = 121
Output: true
Penjelasan: Dibaca dari belakang, 121 tetap 121, jadi jawabannya adalah true.

Input: x = -121
Output: false
Penjelasan: Jika dibaca dari belakang, -121 menjadi 121-, yang merupakan teks berbeda, jadi jawabannya adalah false.

Pertanyaan lanjutan

Bisakah kamu menyelesaikannya tanpa mengubah bilangan bulat menjadi string?

Petunjuk

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

0 dari 3 dibuka

Solusi

Sebuah angka adalah palindrom jika nilainya sama dengan kebalikannya. Sebagai teks, cukup lakukan satu perbandingan. Tanpa teks, menyusun ulang seluruh angka dalam urutan terbalik dapat menyebabkan overflow, jadi balik hanya separuh digit kedua lalu bandingkan dengan separuh digit pertama.

Bandingkan string dengan kebalikannya

Intuisi

Tulis angka sebagai teks lalu bandingkan dengan kebalikannya. Angka negatif tidak memerlukan penanganan khusus: -121 diawali tanda minus dan diakhiri digit, jadi tidak pernah sama dengan kebalikannya 121-.

Teks tersebut memiliki satu karakter untuk setiap digit, sekitar log10(x) karakter dan paling banyak 11 di sini. Biayanya adalah string tambahan.

Algoritma

Ubah x menjadi string s.
Balikkan s.
Kembalikan apakah s sama dengan kebalikannya.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Balikkan separuh dari angka

Intuisi

x % 10 menghasilkan digit terakhir, dan pembagian bilangan bulat dengan 10 menghapusnya. Memindahkan digit dari akhir x ke angka kedua half membentuk kebalikan dari digit yang kamu hapus. Berhenti setelah half setidaknya sama besar dengan sisa x: kamu sudah mengambil setengah digitnya. 1221 berakhir dengan x = 12 dan half = 12, yaitu palindrom. Jika jumlah digitnya ganjil, half juga menyimpan digit tengah: 12321 berakhir dengan x = 12 dan half = 123, jadi kamu membandingkan x dengan half / 10.

Tangani dua kasus sebelum perulangan. Bilangan negatif tidak pernah menjadi palindrom. Bilangan yang berakhir dengan 0 harus diawali dengan 0, dan hanya 0 yang demikian. Tanpa pemeriksaan ini, 10 berakhir dengan x = 0 dan half = 1, sehingga x == half / 10 keliru menghasilkan nilai benar. half tidak pernah melebihi 6 digit, jadi nilainya muat dalam tipe bilangan bulat apa pun.

Algoritma

Jika x negatif, atau berakhir dengan 0 dan bukan 0, kembalikan false.
Atur half = 0.
Selama x > half, atur half = half * 10 + x % 10 lalu bagi x dengan 10 menggunakan pembagian bilangan bulat.
Kembalikan true jika x == half (jumlah digit genap) atau x == half / 10 (jumlah digit ganjil).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Jebakan dan kasus tepi

Lupa menangani bilangan negatif. Dalam bahasa yang mempertahankan tanda pada hasil sisa bagi, membalik -121 menghasilkan -121 dan pemeriksaan berhasil. Di Python, karena -1 // 10 bernilai -1, perulangan while x != 0 tidak pernah berakhir.
Tidak menolak bilangan yang berakhir dengan 0. Pembalikan separuh kemudian menerima 10. 0 sendiri adalah palindrom.
Membalik seluruh bilangan dalam integer 32-bit. Hasil pembalikan 2147483647 tidak muat.
Menggunakan / saat bahasa tersebut membagi dengan hasil pecahan. Gunakan Math.floor(x / 10) di JavaScript, // di Python, %/% di R, dan ~/ di Dart.
Membandingkan hasil pembalikan penuh dengan x setelah perulangan mengubah x. Simpan salinan nilai aslinya.

Pertanyaan yang sering diajukan3

Apakah bilangan negatif merupakan palindrom?

Tidak. Jika dibaca dari belakang, -121 menjadi 121-, dan tanda minus tidak memiliki karakter yang cocok di ujung lainnya. Jadi, setiap bilangan bulat negatif mengembalikan false.

Mengapa hanya membalik setengah dari angka?

Membalik semua digit dapat menyebabkan integer 32-bit mengalami overflow: angka yang dibalik dari 2147483647 lebih besar daripada nilai int terbesar. Setengah digit selalu muat, dan perulangan ini mengerjakan setengahnya saja.

Berapa kompleksitas waktu dari Palindrome Number?

Kedua pendekatan berjalan dalam waktu O(log x), karena angka x memiliki sekitar log10(x) digit dan setiap digit diproses satu kali. Pendekatan string menggunakan ruang tambahan O(log x) untuk teks, sedangkan pembalikan setengah angka menggunakan O(1).

def isPalindrome(x):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

x = 121

Output yang diharapkan

true