Happy Number

Easy Subject: Math & Geometry

Time Complexity

O(log N)

Space Complexity

O(1)

Problem Description

Problem Statement

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, and repeat the process until the number equals 1, or it loops endlessly in a cycle. Return true if n is a happy number.

Example 1:

Input: n = 19
Output: true

Optimal Solution

Python

Approach: Floyd's Cycle Detection

Calculate the sum of squares of digits. Use fast and slow pointers (or numbers) to detect a cycle. If the fast number reaches 1, it's a happy number. If fast and slow meet and it's not 1, there is a cycle, so it's not a happy number.

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

        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