Soal Happy Number nanya apakah kalau digit sebuah angka dikuadratkan lalu dijumlahkan berulang-ulang, hasilnya akhirnya sampai ke 1. Kalau barisannya mengulang sebuah nilai tanpa pernah sampai ke 1, angka itu nggak happy.
Set mencatat angka yang udah muncul. Fast and slow pointer mendeteksi pengulangan yang sama dengan O(1) extra space.
Barisannya
Sebuah angka disebut happy kalau aku bisa terus-terusan:
- Ambil digit-digitnya
- Kuadratkan setiap digit
- Jumlahkan hasil kuadratnya
- Ulangi sampai dapat 1
Kalau aku nggak pernah dapat 1 dan malah masuk ke cycle, angka itu nggak happy.
Versi ini menyimpan setiap hasil di Set dan berhenti saat mencapai 1 atau nilai yang berulang:
function isHappyNaive(n) {
let seen = new Set();
while (n !== 1 && !seen.has(n)) {
seen.add(n);
n = sumOfSquares(n);
}
return n === 1;
}
function sumOfSquares(n) {
let sum = 0;
while (n > 0) {
let digit = n % 10;
sum += digit * digit;
n = Math.floor(n / 10);
}
return sum;
}
Cara ini bisa mendeteksi kedua hasil, tapi set-nya ikut membesar seiring barisannya.
Mendeteksi cycle
Barisan ini bentuknya sama kayak linked list: setiap angka menunjuk ke hasil sumOfSquares berikutnya. Barisan yang happy bakal sampai ke 1. Barisan lainnya pada akhirnya masuk ke cycle, jadi fast and slow pointer bisa membedakan dua kasus itu tanpa menyimpan setiap nilai.
Implementasinya memulai fast satu langkah di depan:
function isHappy(n) {
let slow = n;
let fast = sumOfSquares(n); // Fast starts one step ahead
// Keep going until fast reaches 1 or slow catches up to fast
while (fast !== 1 && slow !== fast) {
slow = sumOfSquares(slow); // Move slow one step
fast = sumOfSquares(sumOfSquares(fast)); // Move fast two steps
}
return fast === 1; // If fast reached 1, it's happy!
}
function sumOfSquares(n) {
let sum = 0;
while (n > 0) {
let digit = n % 10;
sum += digit * digit;
n = Math.floor(n / 10);
}
return sum;
}
Untuk n = 19, pointer-nya bergerak seperti ini:
- slow = 19, fast = sumOfSquares(19) = 82
- slow = 82, fast = sumOfSquares(sumOfSquares(82)) = sumOfSquares(68) = 100
- slow = 68, fast = sumOfSquares(sumOfSquares(100)) = sumOfSquares(1) = 1
fast === 1, jadi function-nya returntrue.
Kalau urutannya masuk ke cycle tanpa 1, slow dan fast akhirnya bertemu di dalamnya. Kalau mencapai 1, loop berhenti dengan fast === 1.
Setiap pemanggilan sumOfSquares memproses digit input-nya. Versi pointer menyimpan variabel dalam jumlah tetap, sedangkan versi Set menyimpan setiap hasil berbeda yang dikunjungi.
Menghitung nilai berikutnya dengan sumOfSquares memungkinkan deteksi cycle yang sama tanpa membuat linked list.

Memuat komentar...