Problem of The Day: Happy Number

2 min read 429 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def isHappy(self, n: int) -> bool:
        x = n
        seen = {x}
        while x != 1:
            next_num = 0
            curr = x
            while curr > 0:
                next_num += (curr % 10) ** 2
                curr //= 10
            if next_num in seen:
                return False
            seen.add(next_num)
            x = next_num

        return x == 1

Time: O(log n) Space: O(log n)

Editorial

Approach 1: Detect Cycles with a HashSet

class Solution:
    def isHappy(self, n: int) -> bool:

        def get_next(n):
            total_sum = 0
            while n > 0:
                n, digit = divmod(n, 10)
                total_sum += digit**2
            return total_sum

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

        return n == 1

Approach 2: Floyd’s Cycle-Finding Algorithm

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit**2
            return total_sum

        slow_runner = n
        fast_runner = get_next(n)
        while fast_runner != 1 and slow_runner != fast_runner:
            slow_runner = get_next(slow_runner)
            fast_runner = get_next(get_next(fast_runner))
        return fast_runner == 1

Time: O(log n) Space: O(1)