Happy Number

EASYProblemSolve External Links

Description

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

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.
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

Example 1

Input: n = 19

Output: true

Explanation:

1² + 9² = 1 + 81 = 82
8² + 2² = 64 + 4 = 68
6² + 8² = 36 + 64 = 100
1² + 0² + 0² = 1 ✓

We reached 1, so 19 is a happy number.

Example 2

Input: n = 2

Output: false

Explanation:

2² = 4
4² = 16
1² + 6² = 37
3² + 7² = 58
5² + 8² = 89
8² + 9² = 145
1² + 4² + 5² = 42
4² + 2² = 20
2² + 0² = 4 ← already seen!

The sequence enters a cycle (4 → 16 → 37 → ... → 20 → 4) that never includes 1, so 2 is NOT a happy number.

Constraints

1 ≤ n ≤ 2³¹ - 1

Editorial

Brute Force - HashSet Cycle Detection

Intuition

The process of replacing a number with the sum of squares of its digits creates a sequence of numbers. This sequence either:

Eventually reaches 1 (happy number), or
Enters a cycle and loops forever (not happy).

The key observation is: the sequence can NEVER grow to infinity. Why? Because even for the largest possible input (2³¹ - 1 ≈ 2.1 billion, a 10-digit number), the maximum digit-square sum is 9² × 10 = 810. So after the first step, the number is at most 810, and the sequence stays bounded. Since the values are bounded, by the Pigeonhole Principle, the sequence must eventually revisit a value — forming a cycle.

The simplest way to detect this cycle is to use a HashSet. Store every number we compute. If we see 1, it's happy. If we see a number that's already in the set, we've found a cycle and it's not happy.

Think of it like leaving breadcrumbs as you walk through a maze. If you step on your own breadcrumb, you know you're going in circles.

Step-by-Step Explanation

Let's trace n = 19 (a happy number):

Step 1: n = 19. Is 19 in seen? No. Add 19 to seen. Compute: 1² + 9² = 82. seen = {19}.

Step 2: n = 82. Is 82 in seen? No. Add 82. Compute: 8² + 2² = 68. seen = {19, 82}.

Step 3: n = 68. Is 68 in seen? No. Add 68. Compute: 6² + 8² = 100. seen = {19, 82, 68}.

Step 4: n = 100. Is 100 in seen? No. Add 100. Compute: 1² + 0² + 0² = 1. seen = {19, 82, 68, 100}.

Step 5: n = 1. Loop condition n != 1 is false. Exit loop. Return true.

Now let's trace n = 2 (NOT happy):

Step 1: n = 2. Add to seen. Compute: 2² = 4. seen = {2}.
Step 2: n = 4. Add. Compute: 4² = 16. seen = {2, 4}.
Step 3: n = 16. Add. Compute: 1² + 6² = 37. seen = {2, 4, 16}.
Step 4: n = 37. Add. Compute: 3² + 7² = 58. seen = {2, 4, 16, 37}.
Step 5: n = 58. Add. Compute: 5² + 8² = 89. seen = {2, 4, 16, 37, 58}.
Step 6: n = 89. Add. Compute: 8² + 9² = 145. seen = {2, 4, 16, 37, 58, 89}.
Step 7: n = 145. Add. Compute: 1² + 4² + 5² = 42. seen = {2, 4, 16, 37, 58, 89, 145}.
Step 8: n = 42. Add. Compute: 4² + 2² = 20. seen = {2, 4, 16, 37, 58, 89, 145, 42}.
Step 9: n = 20. Add. Compute: 2² + 0² = 4. seen = {2, 4, 16, 37, 58, 89, 145, 42, 20}.
Step 10: n = 4. Is 4 in seen? YES! Cycle detected. Return false.

HashSet Cycle Detection — Tracing n=19 — Watch the HashSet grow as we process each number in the sequence. Each number is checked against the set before being added. The sequence terminates when we reach 1.

Algorithm

Create a helper function getNext(n) that computes the sum of squares of digits of n
Initialize an empty HashSet seen
While n != 1 AND n is not in seen:
a. Add n to seen
b. Replace n with getNext(n)
Return n == 1

Helper function getNext(n):

Initialize sum = 0
While n > 0:
- Extract last digit: digit = n % 10
- Add its square: sum += digit * digit
- Remove last digit: n = n / 10
Return sum

Code

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen;
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }

private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
};

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num: int) -> int:
            total = 0
            while num > 0:
                digit = num % 10
                total += digit * digit
                num //= 10
            return total

        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)
        return n == 1

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }

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

Complexity Analysis

Time Complexity: O(log n)

Computing getNext for a number with d digits takes O(d) = O(log n) time. After the first step, the numbers stay bounded (≤ 810 for any input), so subsequent steps take O(1) each. The cycle length is bounded by a constant (at most 810 distinct values before a repeat). Total: O(log n) for the initial computation plus O(1) per subsequent step.

Space Complexity: O(log n)

The HashSet stores at most a bounded number of entries (since values stay below 810 after the first step). In theory, the set size is bounded by a constant. However, the initial number itself has O(log n) digits, so the first computation uses O(log n) space.

Why This Approach Is Not Efficient

The HashSet approach works correctly and is reasonably efficient in practice. However, it uses extra space proportional to the number of unique values in the sequence. While this is bounded by a constant in theory (since the sequence values quickly shrink below 810), the HashSet still requires memory allocation, hashing overhead, and pointer storage.

But here's the deeper insight: this problem is fundamentally a cycle detection problem. The sequence of digit-square sums forms a chain, just like nodes in a linked list. Either the chain reaches 1 (no cycle involving 1) or it loops back to a previously visited number (cycle).

This is exactly the same structure as the classic Linked List Cycle problem! And we know that linked list cycles can be detected in O(1) space using Floyd's Tortoise and Hare algorithm — no HashSet needed.

By using two pointers (slow moving one step, fast moving two steps), we can detect whether the sequence converges to 1 or enters a cycle, with zero extra storage.

Optimal Approach - Floyd's Cycle Detection (Two Pointers)

Intuition

Imagine two runners on a track. The slow runner (tortoise) takes one step at a time, and the fast runner (hare) takes two steps at a time. If the track is a straight line ending at a destination (reaching 1), the fast runner gets there first. But if the track forms a loop, the fast runner will lap the slow runner and they'll eventually meet.

We apply this to our number sequence:

Slow pointer: Computes one digit-square sum per step: slow = getNext(slow)
Fast pointer: Computes two digit-square sums per step: fast = getNext(getNext(fast))

If the sequence reaches 1: The fast pointer hits 1 first (since getNext(1) = 1, it stays there). Eventually the slow pointer catches up, and they both equal 1.

If the sequence has a cycle: The fast pointer enters the cycle first. Since it moves faster, it circles the cycle and eventually catches the slow pointer. They meet at some number that is NOT 1.

After the two pointers meet, we simply check: did they meet at 1? If yes → happy. If no → not happy.

Step-by-Step Explanation

Let's trace n = 19 with Floyd's algorithm:

The sequence is: 19 → 82 → 68 → 100 → 1 → 1 → 1 → ...

Initialize: slow = 19, fast = 19.

Iteration 1:

slow = getNext(19) = 82
fast = getNext(getNext(19)) = getNext(82) = 68
slow ≠ fast (82 ≠ 68). Continue.

Iteration 2:

slow = getNext(82) = 68
fast = getNext(getNext(68)) = getNext(100) = 1
slow ≠ fast (68 ≠ 1). Continue.

Iteration 3:

slow = getNext(68) = 100
fast = getNext(getNext(1)) = getNext(1) = 1
slow ≠ fast (100 ≠ 1). Continue.

Iteration 4:

slow = getNext(100) = 1
fast = getNext(getNext(1)) = 1
slow == fast == 1! They met at 1.

Result: Since they met at 1, return true — 19 is happy.

Now trace n = 2 (not happy):

The cycle is: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

After several iterations of slow (1 step) and fast (2 steps), they eventually meet inside this cycle at a number that is NOT 1. Return false.

Floyd's Tortoise and Hare — Chasing Through the Number Chain — The number sequence forms a chain. Slow pointer moves 1 step, fast moves 2 steps. Watch them converge at 1 for the happy number n=19.

Algorithm

Create a helper function getNext(n) that returns the sum of squares of digits
Initialize slow = n and fast = getNext(n)
While fast != 1 AND slow != fast:
a. slow = getNext(slow) — one step
b. fast = getNext(getNext(fast)) — two steps
Return fast == 1

Why this works:

If the sequence reaches 1, fast gets there first (it moves faster). Since getNext(1) = 1, fast stays at 1. Eventually slow reaches 1 too, and the loop exits because fast == 1.
If there's a cycle not including 1, both pointers enter the cycle. The fast pointer moves 1 position closer to the slow pointer with each iteration (modular arithmetic in the cycle), so they must eventually meet. The loop exits because slow == fast, and since the cycle doesn't include 1, fast != 1, so we return false.

Code

class Solution {
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;
    }

private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
};

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num: int) -> int:
            total = 0
            while num > 0:
                digit = num % 10
                total += digit * digit
                num //= 10
            return total

        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 {
    public boolean 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;
    }

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

Complexity Analysis

Time Complexity: O(log n)

Same as the HashSet approach. The digit-square computation for the initial number takes O(log n) (number of digits). Subsequent numbers are bounded (≤ 810), so each step takes O(1). The number of steps until convergence or cycle detection is bounded by a constant.

Space Complexity: O(1)

This is the key improvement! We only use two integer variables (slow and fast) regardless of the input size. No HashSet, no array, no extra storage. The getNext helper uses O(1) space as well.

Comparison with Brute Force:

	HashSet	Floyd's
Time	O(log n)	O(log n)
Space	O(log n)	O(1)
Extra storage	HashSet of visited numbers	Two integers

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Happy Number

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force - HashSet Cycle Detection

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Floyd's Cycle Detection (Two Pointers)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis