Solution to LeetCode 202 Happy Number
LeetCode 202
Happy Number (Easy) [link]
1] Hash Set. The calculated sum cannot be very large. The only two possibilities are 1) we get into a loop 2) we get 1.
The time complexity O(logn). For example, n = 1000 = 10^3. Then 3 = log 1000, which implies the relationship between the number of digit d and the number n: d-1 = logn.
class Solution:
def isHappy(self, n: int) -> bool:
def calculation(n):
SUM = 0
while n > 0:
SUM += (n % 10) ** 2
n = n // 10
return SUM
SET = set()
while n != 1 and n not in SET:
SET.add(n)
n = calculation(n)
return n == 1
2] Fast and Slow Pointers. Time complexity O(logn). Space complexity O(1).
class Solution:
def isHappy(self, n: int) -> bool:
def calculation(n):
SUM = 0
while n > 0:
SUM += (n % 10) ** 2
n = n // 10
return SUM
slow = n
fast = calculation(n)
while fast != 1 and slow != fast:
fast = calculation(calculation(fast))
slow = calculation(slow)
return fast == 1
