Happy Number

easy hash set cycle detection

Problem

Write an algorithm to determine if a number n is happy. A happy number is a number 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.

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;
}

Explanation

We keep replacing the number with the sum of the squares of its digits and watch what happens. If we ever hit 1, the number is happy. The catch is that an unhappy number loops forever, so we need a way to notice we are going in circles.

The trick is a hash set of numbers we have already seen. Each step, before computing the next value, we record the current one. If a number ever reappears, we are in a cycle that will never reach 1, so we stop and report unhappy.

The helper nxt(x) peels off digits with x % 10, squares each, and adds them up while x //= 10 shrinks the number.

Example: n = 19 → 1²+9² = 82 → 8²+2² = 68 → 6²+8² = 100 → 1²+0²+0² = 1. We reached 1, so 19 is happy.

The loop ends either when n == 1 (return true) or when n is already in seen (a cycle, return false).

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