Sweaty Imposter

Happy Number

EasyFast & Slow Pointers (Floyd's)NeetCode 150JuniorOpen on LeetCodeUpdated

You're given a positive integer n. Replace it with the sum of the squares of its digits, then repeat with the result. n is happy if this process eventually reaches 1 (after which it stays at 1). Otherwise the numbers repeat forever without ever hitting 1, and n is not happy. Return true if n is happy and false if not.

Examples

n = 19 returns true

1^2 + 9^2 = 82, then 8^2 + 2^2 = 68, then 6^2 + 8^2 = 100, then 1^2 + 0^2 + 0^2 = 1. The process reaches 1, so 19 is happy.

n = 2 returns false

The sequence goes 2, 4, 16, 37, 58, 89, 145, 42, 20, and then back to 4. From there it repeats the same eight numbers forever and never reaches 1.

Constraints

  • 1 <= n <= 2^31 - 1

Hints

Hint 1

Repeatedly applying a function either terminates or revisits a value, how do you tell which?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Each number leads to exactly one next number, so the sequence behaves like a linked list. It can't grow without bound (a d-digit number maps to at most 81d), so it either reaches 1 or repeats. Run Floyd's cycle detection: slow applies the step once, fast twice, starting one step ahead. Stop when fast reaches 1 (happy) or catches slow (a loop without 1). Each step costs O(log n) digit work.

Time

O(log n)

Space

O(1)

Pitfall

Don't wait for n itself to come back: unhappy numbers usually fall into a loop that excludes them, like 2 -> 4 -> 16 -> ... -> 4. And if slow and fast both start at n, a `while slow != fast` loop exits before running, so start fast one step ahead.

Solutions

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = next(n);
        while (fast != 1 && slow != fast) {
            slow = next(slow);
            fast = next(next(fast));
        }
        return fast == 1;
    }

    private int next(int x) {
        int sum = 0;
        while (x > 0) {
            int d = x % 10;
            sum += d * d;
            x /= 10;
        }
        return sum;
    }
}
Drill This