Problem statement

https://leetcode.com/problems/happy-number/

Solution

There is straightforward algorithm, where we put all numbers into dictionary with O(n) time and memory.

However if we deal this problem as problem 0141 about cycle in linked list, we can solve it with only O(1) memory, time complexity still be O(n) but 2-3 slower, because we can do 2 full circles for fast iterator and one for slow.

Complexity

Time complexity is O(log n), because it can be proved that each time number in decreased a lot.

Code

class Solution:
    def isHappy(self, n):
        d = set()
        while True:
            n2 = sum(int(dig)**2 for dig in str(n))
            if n2 == 1: return True
            if n2 in d: return False
            d.add(n2)
            n = n2