Happy Number

Solution

First we need to realize that n will not go to infinity after experimented w/ $9...9$.

So there are only 2 cases for n:

1. eventually gets to 1
2. stuck in a cycle

So we need to detect if there is a cycle.

Detect Cycles w/ HashSet

Complexity

time: $O(\log n)$
space: $O(\log n)$ (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

    hashset = set()
    while n != 1 and n not in hashset:
        hashset.add(n)
        n = get_next(n)
    return n == 1

Floyd's Cycle-Finding Algorithm

Repeatedly calling 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: slow and fast. For each step, slow goes forward by 1 number and fast by 2.

If n is a happy number, fast will eventually get to 1. Else, slow and fast will equal.

Complexity

time: $O(\log n)$
space: $O(1)$

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