Happy Number | Problems

Write an algorithm to determine if a number n is happy. A happy number is defined by the following process: starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1, or it loops endlessly in a cycle that does not include 1. Numbers for which this process ends in 1 are happy.

Example 1:

Input: n = 19
Output: true (1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1)

Example 2:

Input: n = 2
Output: false

Sample Input

—

Sample Output

—

Constraints

1 <= n <= 2^31 - 1

Test Cases

Case 1

Args: [19] Expected: true

Case 2

Args: [2] Expected: false

Topics

Matrix BFS DFS

Approach: Floyd's Cycle Detection

Use slow and fast pointers on the digit-square-sum sequence. Compute the next number by summing squares of digits. If fast reaches 1, the number is happy. If slow meets fast without reaching 1, there is a cycle and the number is not happy.

function happyNumber(n) {
  function getNext(num) {
    let sum = 0;
    while (num > 0) {
      const d = num % 10;
      sum += d * d;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  let slow = n, fast = getNext(n);
  while (fast !== 1 && slow !== fast) {
    slow = getNext(slow);
    fast = getNext(getNext(fast));
  }
  return fast === 1;
}

Time Complexity: O(log n)

Space Complexity: O(1)

Saved in this browser only. Private to you.