Squared-Digit Loop to One

easy hash set cycle detection

Problem

A "happy" number is one whose iterated sum-of-squared-digits eventually reaches 1. The sequence either lands on 1 or enters a cycle that never includes 1 — for example, 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. Track every value seen in a hash set; bail out as soon as you revisit one.

Inputn = 19

Outputtrue

19 → 82 → 68 → 100 → 1.

def is_happy(n):
    def nxt(x):
        s = 0
        while x:
            d = x % 10
            s += d * d
            x //= 10
        return s
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = nxt(n)
    return n == 1

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

class Solution {
    private int next(int x) {
        int s = 0;
        while (x > 0) { int d = x % 10; s += d * d; x /= 10; }
        return s;
    }
    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;
    }
}

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

Time: O(log n) per step Space: O(k)