307. Happy Number
Easy
Cycle Detection Set
Hashing
Problem
Starting with a positive integer n, repeatedly replace the number by the sum of the squares of its digits. Return true if the process eventually reaches 1. Return false if it enters a cycle that never reaches 1.
Examples
Example 1
Input: 19
Output: true
Example 2
Input: 2
Output: false
Example 3
Input: 1
Output: true
Constraints
� 1 <= n <= 2147483647
Hints
?? If the process does not reach 1, eventually some value must repeat.
?? Store previously observed values in a set.
?? Alternatively, treat the transformation as a linked-list next function and use Floyd cycle detection.
Expected Complexity
Time: O(log n) per transformation sequence in practice
Space: O(log n)
Follow-up
Can you solve it using O(1) auxiliary space with Floyd's cycle detection?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
19Expected
true