Happy Number | Problems

Determine whether a given positive integer n is a happy number. To test this, repeatedly replace the number with the sum of the squares of its individual digits. If this process eventually lands on 1, the original number is happy; if instead it falls into a repeating cycle that never includes 1, the number is not happy.

Input Format

Implement happyNumber(n). Inputs below show JavaScript function arguments; there is no stdin parsing.

Output Format

Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input

n = 19

Output

true

Example 2

Input

n = 2

Output

false

Constraints

1 <= n <= 2^31 - 1

Test Cases (2)

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.

javascript

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.