Happy Number
easyTime: O(log n)Space: O(1)
Recognize the pattern
repeatedly sum squares of digits until 1 or cycledetect cyclehappy = reaches 1
Brute force idea
Iterate with a hash set to detect cycles — O(log n) per step, O(log n) space.
Better approach
Floyd's cycle detection: slow does one step, fast does two. If they meet at 1, happy. Otherwise, cycle detected. O(1) space.
Key invariant
The digit-square-sum sequence either reaches 1 or enters a cycle. Floyd's detects both without storing history.
Watch out for
Using a hash set works but uses space. Floyd's is O(1) space.