202. Happy Number Easy

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

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.
• Return true if n is a happy number, and false if not.

Example 1:
Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:
Input: n = 2
Output: false

Approach

Input: A number n

Output: Verify if n is a happy number

This is a Hash Set || Fast & Slow Pointers problem.

We can solve this problem using either a hash set or fast and slow pointers.

First, we create a function next to repeatedly perform the "sum of squares of digits" transformation on the current number and return the next transformed value.

Hash Set

• We can use a hash set to record the values after each transformation.
• If an intermediate value reappears, it means it has entered a cycle and is not a happy number.
• If the required transformation eventually results in 1, it is a happy number.

Fast & Slow Pointers

• The slow pointer takes one step at a time (one transformation), while the fast pointer takes two steps at a time.
• If they meet at 1 -> Happy number; if they meet at any other number -> A cycle exists, and it's not a happy number.
• Advantage: O(1) extra space.

Implementation

Hash Set Approach

python

class Solution:
    def isHappy(self, n: int) -> bool:
        # Use a set to store the numbers that have appeared to prevent infinite loops
        seen = set()

        # Define a function to calculate the "sum of squares of digits" of a number
        def next(num):
            s = 0
            while num > 0:
                d = num % 10        # Extract the last digit of the current number
                s += d ** 2         # Add the square of this digit
                num = num // 10     # Remove the last digit
            return s

        # Keep transforming while n is not 1 and has not appeared before
        while n != 1 and n not in seen:
            seen.add(n)      # Record the current number to prevent infinite loops
            n = next(n)      # Get the number for the next round
        
        # If n finally equals 1, it's a happy number, otherwise it's not
        return n == 1

javascript

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    const seen = new Set();

    function next(num) {
        let sum = 0;

        while (num > 0) {
            let d = num % 10;
            sum += d ** 2;
            num = Math.floor(num / 10);
        }

        return sum;
    }

    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = next(n);
    }

    return n === 1;
};

Fast & Slow Pointers Approach

python

class Solution:
    def isHappy(self, n: int) -> bool:
        # Define a function to calculate the "sum of squares of digits" of a number
        def next(num):
            s = 0
            while num > 0:
                d = num % 10        # Extract the last digit
                s += d ** 2         # Add its square
                num = num // 10     # Remove the last digit
            return s
        
        # Initialization of fast and slow pointers
        # slow takes one step at a time (calculates sum of squares once)
        # fast takes two steps at a time (calculates sum of squares twice)
        slow, fast = n, next(n)

        # Loop until:
        # 1. fast pointer reaches 1 (meaning it's a happy number)
        # 2. slow and fast pointers meet (meaning a cycle is entered, not a happy number)
        while fast != 1 and slow != fast:
            slow = next(slow)           # Slow pointer takes one step
            fast = next(next(fast))     # Fast pointer takes two steps
        
        # If fast eventually reaches 1, then it's a happy number
        return fast == 1

javascript

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    function next(num) {
        let s = 0;

        while (num > 0) {
            const d = num % 10;
            s += d ** 2;
            num = Math.floor(num / 10);
        }

        return s;
    }

    let slow = n;
    let fast = next(n);
    while (fast !== 1 && slow !== fast) {
        slow = next(slow);
        fast = next(next(fast));
    }

    return fast === 1;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

202. Happy Number (English)202. 快乐数 (Chinese)