Solution 1 - HashSet Cycle Detection

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1. If the process enters a cycle that never includes 1, the number is not happy. Use a set to track previously seen numbers and detect cycles.

TimeComplexity: O(logn)

SpaceComplexity: O(logn)

""" 0202.1 - Happy Number - Solution 1 - HashSet Cycle Detection """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isHappy(self, n: int) -> bool:
        """Happy Number Function"""
        seen = set()

        while n != 1:
            if n in seen:
                return False
            seen.add(n)
            n = sum(int(d) ** 2 for d in str(n))

        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isHappy(19))   # True
    print(Solution().isHappy(2))    # False
    print(Solution().isHappy(7))    # True
    print(Solution().isHappy(1))    # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Floyd's Cycle Detection (Fast and Slow Pointer)

Instead of using extra space to store seen numbers, use two pointers: a slow pointer that computes the digit square sum once per step and a fast pointer that computes it twice per step. If they meet at 1, the number is happy. If they meet at any other value, a cycle exists and the number is not happy.

TimeComplexity: O(logn)

SpaceComplexity: O(1)

""" 0202.2 - Happy Number - Solution 2 - Floyd's Cycle Detection """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isHappy(self, n: int) -> bool:
        """Happy Number Function"""

        def get_next(number: int) -> int:
            return sum(int(d) ** 2 for d in str(number))

        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


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isHappy(19))   # True
    print(Solution().isHappy(2))    # False
    print(Solution().isHappy(7))    # True
    print(Solution().isHappy(1))    # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0202 - Happy Number

Solution 1 - HashSet Cycle Detection

Solution 2 - Floyd's Cycle Detection (Fast and Slow Pointer)