Question
A positive number is given. Each digit should multiply by itself and calculate the sum of them, which is called "happy number". And then, this process will continue until the result of the sum is one. when found, return true. Otherwise, return false, which means that this operation never ends up.
Solution
You should calculate this process and store the return value into a set-list. If the number is already included in the list, return false. If the sum is one, return true.
Also, you should not convert the number into a string when you calculate "happy number". I don't think it is efficient at the thought of the operation speed.
Submission
Here is the result.
Runtime: 28 ms, faster than 88.07% of Python3 online submissions for Happy Number.
Memory Usage: 13.8 MB, less than 5.26% of Python3 online submissions for Happy Number.
Time complexity: O(n)
Space complexity: O(n)
My code is supposed to store all results into a set-list, so space complexity is gonna be O(n).
This is my code.
def isHappy(self, n: int) -> bool:
check: Set[int] = set()
while n not in check:
check.add(n)
nxt: int = 0
while n > 0:
nxt += (n % 10) ** 2
n = n // 10
n = nxt
return n == 1
https://github.com/nk18chi/leetcode/blob/master/solutions/happy_number/index.py
Bonus
Time complexity can be O(1) if you solve this by Floyd's cycle-finding algorithm. For this, you should prepare for two pointers. One pointer moves step by one and another move two each step. And if the result of both is equal before the faster one is one, return false.
