LC202 Happy Number

class Solution:
    def isHappy(self, n: int) -> bool:
        # main idea: use set() to check circle
        # time O(lgN)  space O(N)
        # step1,  initial a visit set to check if  there is a cycle 
        # step2, edge case:  n = 1 ,otherwise enter the loop
        # step3, store n in the record visit 
        # step4 use str => int convertion, list and sum() to sum up each digit's power of 2;  get new n, enter next loop  
        visited = set()
        if n == 1:
            return True
        else:
            #check if there is a loop
            while n not in visited:
                visited.add(n)
                n = sum([int(x)**2 for x in str(n)])
                if n == 1:
                    return True
            return False 
                

class Solution:
    def isHappy(self, n: int) -> bool:
        #main idea: if process will end up becoming 1, it will be a cycle states;  if loop is endless, it will also be a cycle ==>  essentially the goal is to detect cycle and check if the stage becoming a cycle, if the sum number == 1. can use fast slow (pointer) to record the pace of both process. Theorily, those two will eventually meet no matter how.  =>  Floyd's cycle detection algorithm  
        # time O(N)  spaceO(1)
        fast = n
        slow = n
        def getNext(n):
            total = 0
            while n>0:
                temp = n%10
                total += temp*temp
                n = n//10
            return total
        while True:
            slow = getNext(slow)
            fast = getNext(fast)
            fast = getNext(fast)
            if fast == slow:
                break
        return slow == 1