First we need to realize that
n will not go to infinity after experimented w/
So there are only 2 cases for
- eventually gets to 1
- stuck in a cycle
So we need to detect if there is a cycle.
# Detect Cycles w/ HashSet
due to the HashSet
def isHappy(self, n: int) -> bool: def get_next(n): csum = 0 while n > 0: n, digit = divmod(n, 10) csum += digit**2 return csum st = set() while n != 1 and n not in st: st.add(n) n = get_next(n) return n==1
# Floyd's Cycle-Finding Algorithm
get_next(n) is like a linked list but we don't have to store nodes and pointers.
Floyd's Cycle-Finding Algorithm has 2 runners:
fast. For each step,
slow goes forward by 1 number and
fast by 2.
n is a happy number,
fast will eventually get to
fast will equal.
def isHappy(self, n: int) -> bool: def get_next(n): csum = 0 while n > 0: n, digit = divmod(n, 10) csum += digit**2 return csum slow = n fast = get_next(n) while fast!=1 and slow!=fast: slow = get_next(slow) fast = get_next(get_next(fast)) return fast==1