202. Happy Number

Description

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.

Example 1:

• Input: n = 19
• Output: true
• Explanation:
  1² + 9² = 82
  8² + 2² = 68
  6² + 8² = 100
  1² + 0² + 0² = 1

Example 2:

• Input: n = 2
• Output: false

Constraints:

• 1 <= n <= 2³¹ - 1

Submitted Code

class Solution:
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        seen = set()        # 이미 나온 숫자를 저장할 집합

        while n != 1:
            if n in seen:       # 이미 seen에 있는 숫자면 무한루프 → False
                return False
            seen.add(n)         # 아직 seen에 없는 숫자면 추가

            sum = 0   
            while n > 0:
                sum += (n % 10) ** 2
                n //= 10
            n = sum             # 자리수별로 제곱한 값의 합을 새 n으로 업데이트
        return True         # n이 1이 되면 True 반환

Runtime: 0 ms | Beats 100.00%
Memory: 12.30 MB | Beats 98.64%

중복을 허용하지 않는 set() 집합으로 푸는 방법이다.

n       seen                                   sum      
2       {2}                                    22 = 4
4       {2, 4}                                 42 = 16  
16      {2, 4, 16}                             12 + 62 = 37  
37      {2, 4, 16, 37}                         32 + 72 = 58 
58      {2, 4, 16, 37, 58}                     52 + 82 = 89    
89      {2, 4, 16, 37, 58, 89}                 82 + 92 = 145 
145     {2, 4, 16, 37, 58, 89, 145}            12 + 42 + 52 = 42  
42      {2, 4, 16, 37, 58, 89, 145, 42}        42 + 22 = 20 
20      {2, 4, 16, 37, 58, 89, 145, 42, 20}    22 + 02 = 4 
4       seen에 있는 숫자이므로 false

Other Solutions

1st

class Solution:
    def isHappy(self, n: int) -> bool:
        current = n
        while current > 9:
            sum_of_squares = sum(int(digit) ** 2 for digit in str(current))
            current = sum_of_squares
        return current == 1 or current == 7

time complexity: 𝑂(log𝑛)
space complexity: 𝑂(1)

10보다 작은 일의 자리의 숫자 중에서 무한루프없이 happy number에 도달할 수 있는 숫자는 1과 7뿐이라는 원리를 이용하면 해시 테이블이나 플로이드의 알고리즘 없이 쉽게 해결할 수 있다.

2nd

class Solution:
    def isHappy(self, n: int) -> bool:    
        
        def get_next_number(n):
            output = 0
            
            while n:
                digit = n % 10
                output += digit ** 2
                n = n // 10
            
            return output

        slow = get_next_number(n)                   # 1번 이동
        fast = get_next_number(get_next_number(n))  # 2번 이동

        while slow != fast:     # 두 포인터가 만나기 전까지 반복
            if fast == 1: return True       # fast가 1이면 바로 True 반환
            slow = get_next_number(slow)
            fast = get_next_number(get_next_number(fast))

        return slow == 1                    # while문 종료 후 slow가 1이면 True 반환

플로이드의 거북이와 토끼 알고리즘으로 사이클을 탐지하는 방법.