Happy Number
Detect happiness (square-digit-sum converges to 1) vs cycle via Floyd's two-pointer technique.
Problem#
A number is happy if iterating “replace by sum of squares of digits” eventually reaches 1; otherwise the iteration cycles forever. Return true iff n is happy.
Examples#
19→true(19 → 82 → 68 → 100 → 1)2→false(2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → …cycles)
Constraints#
1 <= n <= 2^31 - 1.
Hints#
Hint 1
Approach#
Treat next(x) = sum of squares of digits of x as the step function. Apply Floyd’s: slow = next(slow), fast = next(next(fast)). If fast reaches 1, happy. If slow == fast before that, cycle → unhappy.
Solution#
class Solution {public: bool isHappy(int n) { auto next = [](int x) { int s = 0; while (x) { int d = x % 10; s += d * d; x /= 10; } return s; }; int slow = n, fast = next(n); while (fast != 1 && slow != fast) { slow = next(slow); fast = next(next(fast)); } return fast == 1; }};func isHappy(n int) bool { next := func(x int) int { s := 0 for x > 0 { d := x % 10 s += d * d x /= 10 } return s } slow, fast := n, next(n) for fast != 1 && slow != fast { slow = next(slow) fast = next(next(fast)) } return fast == 1}class Solution: def isHappy(self, n: int) -> bool: def nxt(x: int) -> int: s = 0 while x > 0: d = x % 10 s += d * d x //= 10 return s
slow, fast = n, nxt(n) while fast != 1 and slow != fast: slow = nxt(slow) fast = nxt(nxt(fast)) return fast == 1function isHappy(n) { const next = (x) => { let s = 0; while (x > 0) { const d = x % 10; s += d * d; x = Math.floor(x / 10); } return s; }; let slow = n, fast = next(n); while (fast !== 1 && slow !== fast) { slow = next(slow); fast = next(next(fast)); } return fast === 1;}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 s = 0; while (x > 0) { int d = x % 10; s += d * d; x /= 10; } return s; }}function isHappy(n: number): boolean { const next = (x: number): number => { let s = 0; while (x > 0) { const d = x % 10; s += d * d; x = Math.floor(x / 10); } return s; }; let slow = n, fast = next(n); while (fast !== 1 && slow !== fast) { slow = next(slow); fast = next(next(fast)); } return fast === 1;}Editorial#
The square-digit-sum function is a deterministic map on small integers (bounded by ~243 for 9-digit values then collapsing further), so the sequence eventually enters either a fixed point (1) or a cycle. Two-pointer detection beats a hash set in space, and is the cleanest framing of “find absorbing state or cycle”.
Complexity#
- Time: O(log n) per step; total iterations are bounded by a small constant.
- Space: O(1).
Concept revision#
Related#