Solution 1
class Solution:
def isHappy(self, n: int) -> bool:
ans = 0
start = n
sums = set()
while n not in sums and ans != 1:
sums.add(n)
ans = self.sumofsquares(n)
n = ans
return ans == 1
def sumofsquares(self, n) -> int:
s = 0
while n > 0:
s += (n % 10) ** 2
n = n // 10
return s
Time complexity is O(1). Space complexity is O(1).
Solution 2
class Solution:
def isHappy(self, n: int) -> bool:
sums = set()
while n not in sums:
sums.add(n)
n = sum(int(i)**2 for i in str(n))
return n == 1
Time complexity is O(1). Space complexity is O(1).
How to calculate the complexity?
Input is a positive integer. Assume it is 32 bit. So we calculate maximum of 10 digits. Assume it is maximum 10 digits 9^2 +9^2…. The sum is 10*81 = 810. Thus, we will calculate maximum of 3 digits. Assume it is 999. We will calculate maximum of 3 digits too….. loops m times. Time complexity is O(m+m(find in set)). Space complexity is O(m(set)). m should smaller than 999. In fact m is 16. m << maximal n. So, Time complexity is O(1). Space complexity is O(1).
步步发财 