Happy Number [Easy] — HashSet Cycle Detection

Problem Statement

A happy number eventually reaches 1 when repeatedly replacing it with the sum of squares of its digits. If it loops endlessly, it's not happy.

Input: 19 → true  (1²+9²=82 → 68 → 100 → 1)
Input: 2  → false

Intuition

HashSet: Store seen numbers. If 1 → happy. If duplicate → unhappy.

Floyd: Slow/fast pointers on the sequence (no extra space).

Solutions

C++

int digitSquareSum(int n){int s=0;while(n){int d=n%10;s+=d*d;n/=10;}return s;}
bool isHappy(int n) {
    unordered_set<int> seen;
    while(n!=1&&!seen.count(n)){seen.insert(n);n=digitSquareSum(n);}
    return n==1;
}

Java

public boolean isHappy(int n) {
    Set<Integer> seen=new HashSet<>();
    while(n!=1&&seen.add(n)) n=digitSquare(n);
    return n==1;
}
int digitSquare(int n){int s=0;while(n>0){int d=n%10;s+=d*d;n/=10;}return s;}

JavaScript

var isHappy = function(n) {
    const sq=n=>{let s=0;while(n){const d=n%10;s+=d*d;n=Math.floor(n/10);}return s;};
    const seen=new Set();
    while(n!==1&&!seen.has(n)){seen.add(n);n=sq(n);}
    return n===1;
};

Python

def isHappy(n: int) -> bool:
    def digit_sq(x):
        s = 0
        while x:
            x, d = divmod(x, 10)
            s += d*d
        return s
    seen = set()
    while n != 1:
        if n in seen: return False
        seen.add(n)
        n = digit_sq(n)
    return True

# Floyd's algorithm (O(1) space):
def isHappy_floyd(n: int) -> bool:
    def sq(x): return sum(int(d)**2 for d in str(x))
    slow, fast = n, sq(n)
    while fast != 1 and slow != fast:
        slow = sq(slow); fast = sq(sq(fast))
    return fast == 1

Complexity

Time: O(log n) per step, O(log n) total steps
Space: O(log n) HashSet; O(1) Floyd