A non-cyclical number is an integer defined by the following algorithm:
- Given a positive integer, replace it with the sum of the squares of its digits.
- Repeat the above step until the number equals
1, or it loops infinitely in a cycle which does not include1. - If it stops at
1, then the number is a non-cyclical number.
Given a positive integer n, return true if it is a non-cyclical number, otherwise return false.
Example 1:
Input: n = 100
Output: trueExplanation: 1² + 0² + 0² = 1
Example 2:
Input: n = 101
Output: falseExplanation:1² + 0² + 1² = 22² = 44² = 161² + 6² = 373² + 7² = 585² + 8² = 898² + 9² = 1451² + 4² + 5² = 424² + 2² = 202² + 0² = 4 (This number has already been seen)
Constraints:
1 <= n <= 1000
Topics
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(logn) time and O(logn) space, where n is the given integer.
Hint 1
Create a helper function that returns the sum of the squares of a number's digits. Then, simulate the given process. If we reach 1, return true. However, we may get stuck in a cycle if a number is processed more than once. What data structure can be used to detect if a number has already been processed?
Hint 2
We can use a hash set to detect if a number has already been processed. At each step, we update n with the return value of the helper function. If the result is 1, we return true. If n is already in the set, we return false. Otherwise, we add n to the hash set and continue.