Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0202 - Happy Number
    0202 - Happy Number
    0202 - Happy Number
    0202 - Happy Number

    0202 - Happy Number

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/happy-number/

    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)TimeComplexity: O(logn)TimeComplexity:O(logn)
    SpaceComplexity:O(logn)SpaceComplexity: O(logn)SpaceComplexity:O(logn)

    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)TimeComplexity: O(logn)TimeComplexity:O(logn)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 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()

    """ 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()