Happy Number

Q: Berapa kompleksitas waktu Happy Number?

O(log n) . Langkah pertama membaca O(log n) digit dari n ; setiap nilai berikutnya kurang dari 1000, dan tidak ada lintasan yang mengunjungi lebih dari 20 angka sebelum mencapai 1 atau berulang. hash set menyimpan angka-angka tersebut, dan versi Floyd menggunakan ruang O(1) .

MudahPointer cepat dan lambat Hashing

+10

Mulai dari bilangan bulat positif n, lalu ganti nilainya dengan jumlah kuadrat digit-digitnya secara berulang. Contohnya, 12 menjadi 1² + 2² = 5. Jika proses ini mencapai 1, n adalah bilangan bahagia. Jika tidak, proses ini akan terus berputar melalui angka-angka yang tidak pernah mencakup 1. Kembalikan true jika n adalah bilangan bahagia dan false jika bukan.

Fungsi

isHappy(n: integer) → boolean

ninteger: bilangan bulat positif yang akan diuji
Mengembalikanboolean: benar jika mengulangi jumlah kuadrat digit mencapai 1, salah jika terus berulang tanpa henti

Batasan

1 ≤ n ≤ 2³¹-1

Contoh

Input: n = 7
Output: true
Penjelasan: 7 menjadi 49, lalu 4² + 9² = 97, lalu 130, lalu 10, lalu 1. Proses ini mencapai 1, jadi 7 adalah bilangan bahagia.

Input: n = 2
Output: false
Penjelasan: 2 menjadi 4, 16, 37, 58, 89, 145, 42, 20 lalu kembali menjadi 4. Setelah itu, delapan angka yang sama terus berulang selamanya dan tidak pernah mencapai 1.

Input: n = 100
Output: true
Penjelasan: 1² + 0² + 0² = 1, jadi 100 mencapai 1 setelah satu langkah.

Pertanyaan lanjutan

Bagaimana cara menghitung bilangan bahagia dari 1 sampai 10^6 dengan cepat, menggunakan kembali jawaban untuk bilangan di bawah 1000 alih-alih menelusuri setiap bilangan awal dari nol?

Petunjuk

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

0 dari 3 dibuka

Solusi

Perulangan ini tidak dapat bertambah tanpa batas: bilangan 10 digit memetakan ke paling banyak 10 × 81 = 810, dan bilangan di bawah 1000 memetakan ke paling banyak 243. Jadi, nilainya tetap berada di antara kurang dari 1000 nilai dan pasti mencapai 1 atau berulang. Ini menjadikannya deteksi siklus: ingat apa yang sudah kamu lihat, atau jalankan penelusur lambat dan cepat.

Ingat setiap angka yang pernah kamu lihat

Intuisi

Simpan setiap angka yang kamu kunjungi dalam hash set, lalu berhenti saat mencapai 1 atau menemukan angka yang berulang. Angka berikutnya hanya bergantung pada angka saat ini, jadi setelah suatu angka muncul kembali, semua angka setelahnya akan berulang dan 1 tidak akan pernah muncul. Untuk 2, set terisi dengan 2, 4, 16, 37, 58, 89, 145, 42, dan 20, lalu nilai berikutnya, 4, sudah ada di dalamnya.

Setelah langkah pertama, setiap nilai kurang dari 1000, jadi array flag dengan 1000 entri dapat menggantikan set.

Algoritma

Buat set hash kosong seen.
Selama n bukan 1, kembalikan false jika n ada di seen.
Jika tidak, tambahkan n ke seen dan ganti n dengan jumlah kuadrat digit-digitnya.
Saat perulangan berakhir, n adalah 1: kembalikan true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Pejalan cepat dan lambat (deteksi siklus Floyd)

Intuisi

Setiap angka memiliki satu panah menuju jumlah kuadrat digitnya, jadi perjalanan dari n akan mencapai 1 atau masuk ke dalam perulangan. Metode Floyd menemukan perulangan tanpa penyimpanan: slow mengambil satu langkah setiap putaran dan fast mengambil dua langkah.

Jika perulangan tidak melewati 1, kedua pelari akhirnya akan berputar mengelilinginya, dan setiap putaran fast bertambah satu langkah, sehingga keduanya tiba di angka yang sama: untuk 2, mereka bertemu di 42 setelah tujuh putaran. Jika perjalanan mencapai 1, fast tiba lebih dulu dan tetap di sana, karena 1 dipetakan ke 1. Untuk 7, fast bergerak melalui 49, 130, 1 sementara slow masih berada di 97. Jumlah putarannya adalah kelipatan kecil dari panjang perjalanan, dan memorinya membutuhkan dua bilangan bulat.

Algoritma

Buat helper yang mengembalikan jumlah kuadrat digit suatu angka.
Tetapkan slow = n dan tetapkan fast ke angka satu langkah setelah n.
Selama fast bukan 1 dan slow berbeda dari fast, gerakkan slow satu langkah dan fast dua langkah.
Kembalikan apakah fast adalah 1.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Jebakan dan kasus tepi

Melakukan perulangan sampai nilainya 1 tanpa kondisi keluar lainnya. Untuk 2, perulangan itu tidak pernah berakhir.
Memulai kedua pelacak pada angka yang sama dan menguji slow != fast sebelum langkah pertama. Perulangan tidak pernah berjalan, dan 7 dinyatakan bukan bilangan bahagia.
Mengembalikan slow == 1. Untuk 7, fast mencapai 1 dan perulangan berhenti saat slow berada di 97.
Menyatakan n bukan bilangan bahagia setiap kali kedua pelacak bertemu. Keduanya juga bertemu di 1, jadi periksa di mana mereka bertemu.
Menjumlahkan digit-digitnya, atau menguadratkan seluruh angkanya. Untuk 12, nilai berikutnya adalah 1² + 2² = 5, bukan 3 dan bukan 144.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Happy Number?

O(log n). Langkah pertama membaca O(log n) digit dari n; setiap nilai berikutnya kurang dari 1000, dan tidak ada lintasan yang mengunjungi lebih dari 20 angka sebelum mencapai 1 atau berulang. hash set menyimpan angka-angka tersebut, dan versi Floyd menggunakan ruang O(1).

Mengapa semua bilangan yang tidak bahagia akhirnya menjadi 4?

Memeriksa setiap angka di bawah 1000 menunjukkan satu perulangan yang tidak mencapai 1: 4, 16, 37, 58, 89, 145, 42, 20 lalu kembali ke 4. Setiap angka awal menjadi kurang dari 1000 setelah satu langkah, jadi setiap angka yang tidak bahagia akan masuk ke perulangan ini. Berhenti di 4 bisa dilakukan, tetapi kamu harus membuktikan fakta itu dalam wawancara.

Apa hubungan Happy Number dengan Linked List Cycle?

Keduanya menanyakan apakah mengikuti satu panah dari setiap item akan membawa kembali ke item yang sudah dikunjungi. Di sini, panahnya adalah jumlah kuadrat digit; dalam linked list, panahnya adalah pointer berikutnya. Itulah sebabnya penelusur cepat dan lambat dapat menyelesaikan keduanya dengan memori konstan.

def isHappy(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 7

Output yang diharapkan

true