Happy Number

Problem Description

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.

Examples

Constraints

• 1 ≤ n ≤ 2³¹ - 1

Cycle Detection (Floyd’s Tortoise and Hare)

The sequence of numbers generated by summing squared digits will eventually either reach 1 or enter a cycle of repeating values.

We can model this as a cycle detection problem (similar to Linked List Cycle). We keep a slow and a fast pointer.

• slow calculates the next value once per step: slow = getNext(slow)
• fast calculates the next value twice per step: fast = getNext(getNext(fast))

If fast reaches 1, the number is happy. If there is a cycle, the slow and fast pointers will eventually meet at some number other than 1.

Solution: Floyd’s Cycle Detection

class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(slow);

        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }

        return fast == 1;
    }

    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            totalSum += d * d;
            n /= 10;
        }
        return totalSum;
    }
}

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(val: int) -> int:
            total_sum = 0
            while val > 0:
                val, digit = divmod(val, 10)
                total_sum += digit * digit
            return total_sum

        slow = n
        fast = get_next(n)

        while fast != 1 and slow != fast:
            slow = get_next(slow)
            fast = get_next(get_next(fast))

        return fast == 1

class Solution {
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            totalSum += d * d;
            n /= 10;
        }
        return totalSum;
    }

public:
    bool isHappy(int n) {
        int slow = n;
        int fast = getNext(n);

        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }

        return fast == 1;
    }
};

Complexity Analysis:

• Time Complexity: O(log N). The number of steps is proportional to the number of digits. The largest value a 32-bit integer can produce after one step is 9² * 10 = 810, so values quickly collapse into a small range and loop or terminate in under 100 iterations.
• Space Complexity: O(1) space.

← All Problems