LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Happy Number

Pakai cycle detection untuk mengecek apakah jumlah kuadrat digit yang dihitung berulang-ulang bakal sampai ke 1.

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:

  1. Ambil digit-digitnya
  2. Kuadratkan setiap digit
  3. Jumlahkan hasil kuadratnya
  4. 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:

javascript
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:

javascript
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 return true.

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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan