Non-Cyclical Number
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^2 + 0^2 + 0^2 = 1
Example 2:
Input: n = 101
Output: falseExplanation:
1^2 + 0^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4 (This number has already been seen)
Constraints:
1 <= n <= 1000
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.