Leetcode :: Happy Number

Problems

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Guess

• Floyd's cycle detection algorithm 을 사용하자. (일명 토끼와 거북이 알고리즘)

• 토끼의 digit sum 값이 1이라면 Happy Number가 확실하므로 멈춘다.

• 거북이와 토끼가 같아지는 순간이 오고 토끼가 1이 아니라면 사이클이 탐지된 것 -> Happy Number가 아니다.

Floyd's cycle detection algorithm은
토끼와 거북이가 원형의 트랙에서 멈추지 않고 경주할 때 (cycle)
토끼가 더 빠르므로 거북이와 반드시 같은 위치에서 만나게 된다는 원리.

Solution

def next_num(n):
    ret = 0
    while n != 0:
        q,r = divmod(n,10)
        ret += r*r
        n = q

    return ret


class Solution:
    def isHappy(self, n: int):
        slow = n
        fast = next_num(n)

        while slow != fast and fast != 1:
            slow = next_num(slow)
            fast = next_num(next_num(fast))

        return fast == 1