Solusi Leetcode - Happy Number

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.

Solusi pertama saya pakai Set untuk mencatat angka yang udah pernah muncul. Versi fast and slow pointer pakai ide cycle yang sama, dengan extra space O(1).

Barisannya

Sebuah angka disebut happy kalau saya bisa terus-terusan:

1. Ambil digit-digitnya
2. Kuadratkan setiap digit
3. Jumlahkan hasil kuadratnya
4. Ulangi sampai dapat 1

Kalau saya nggak pernah dapat 1 dan malah masuk ke cycle, angka itu nggak happy.

Versi pertama saya menyimpan setiap nilai di Set. Versi ini berhenti di 1 atau di nilai yang udah ada di set:

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

Kalau barisannya punya cycle, slow dan fast pada akhirnya bakal ketemu di dalam cycle itu. Kalau barisannya sampai ke 1, loop berhenti dengan fast === 1. Variabel pointer bikin extra space tetap O(1), bukan O(n) seperti set yang dipakai di versi baseline.

Saya nggak nyangka bakal pakai algoritma cycle detection untuk soal number theory ini. Setiap panggilan ke sumOfSquares memproses digit-digit dari input-nya, dan loop pointer-nya cuma pakai extra storage yang konstan.

Ide yang bisa dipakai ulang di sini adalah memperlakukan barisan hasil perhitungan sebagai rantai node. Asal nilai berikutnya deterministik, fast and slow pointer bisa mendeteksi cycle tanpa visited set.