160. Happy Number

Repeatedly replace n by the sum of the squares of its digits. If you ever reach 1 it's happy; if you revisit a number you've seen before, you're in a cycle that never hits 1, so it's not.

Idea

The process 'replace n by the sum of the squares of its digits' either reaches 1 (happy) or enters a cycle (unhappy). The only way to detect an endless loop is to notice we've returned to a number we already produced. A seen set records every value we visit; the moment a value repeats, we're cycling.

The values stay small (any number's digit-square-sum drops well below 1000 quickly), so the set never grows large.

Algorithm

1. Keep a seen set.
2. While n != 1 and n is not already in seen:
   • Add n to seen.
   • Replace n with the sum of the squares of its digits.
3. Return true if the loop ended because n == 1, else false (we hit a repeat).

Worked example: n = 19

Reached 1 → 19 is happy → true.

An unhappy number like 2 cycles 2→4→16→37→58→89→145→42→20→4… and revisits 4, so the seen-set catches the loop and we return false.

Complexity

• Time: O(log n) per step with a bounded number of steps → effectively O(log n).
• Space: O(log n) for the seen set (bounded, since values stay small).

import java.util.HashSet;
import java.util.Set;

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

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