Happy Numbers

Write an algorithm to determine if a number n is a happy number.

Happy Number Problem

What Is the Problem?

We want to check if a number is a happy number. Here is the process:

• Start with the number n.
• Replace it with the sum of the squares of its digits.
• Keep repeating this step.

Two things can happen:

• The number becomes 1. This means n is a happy number.
• The numbers start repeating in a cycle (loop). This means n is not a happy number.

We need to return:

• TRUE if n is a happy number.
• FALSE if it is not.

Constraints

• n can be any number from 1 to 2³¹ − 1.

Examples

Example 1

Input: n = 23

We reached 1. So this number is a happy number.

Output: TRUE

Example 2

Input: n = 2

The sequence keeps going like this:

16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

The number 4 has already appeared before. This means there is a cycle (loop). So 2 is not a happy number.

Output: FALSE

Solution

We can solve this problem using the classic fast pointer and slow pointer method.

• The fast pointer moves two steps ahead of the slow pointer.
• We check two things at every step:
  • If the fast pointer becomes 1, the number is a happy number.
  • If the fast pointer becomes equal to the slow pointer, there is a loop. This means the number is not a happy number.

Code

function isHappyNumber(n) {
  // Helper function that calculates the sum of squared digits.
  function sumOfSquaredDigits(number) {
    let totalSum = 0;
    while (number > 0) {
      let temp = Math.floor(number / 10),
          digit = number % 10;
      number = temp;
      totalSum += digit ** 2;
    }
    return totalSum;
  }

  let slowPointer = n;
  let fastPointer = sumOfSquaredDigits(n);

  while (fastPointer !== 1 && slowPointer !== fastPointer) {
    slowPointer = sumOfSquaredDigits(slowPointer);
    fastPointer = sumOfSquaredDigits(sumOfSquaredDigits(fastPointer));
  }

  if (fastPointer == 1) {
    return true;
  }
  return false;
}

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)