Happy Number

Problem Summary

• Given a number n, determine if it is happy. Happy number means the sum of its squares in a loop will eventually lead to 1.

What is Being Asked?

(One sentence on the actual task.)

• Find the linked list cycle. If one exists return False else True.

Main Concepts Used

• Linked List
• Sets
• Fast & Slow Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each item once
• Space: $O(n)$ → Reason: Potentially storing all items generated

Code

class Solution:
    def isHappy(self, n: int) -> bool:
        visited = set()
        while n != 1:
            n = self.sumOfSquares(n)
            if n in visited: 
                return False
            visited.add(n)
        return True
    
    def sumOfSquares(self, n) -> int:
        digits = list(str(n))
        result = 0
        for digit in digits:
            digit = int(digit)
            square = digit ** 2
            result += square
        return result

Optimized Code

class Solution:
    def isHappy(self, n: int) -> bool:
        slow, fast = n, self.sumOfSquares(n)

        while slow != fast:
            slow = self.sumOfSquares(slow)
            fast = self.sumOfSquares(self.sumOfSquares(fast))
        
        return fast == 1
    
    def sumOfSquares(self, n) -> int:
        digits = list(str(n))
        result = 0
        for digit in digits:
            digit = int(digit)
            square = digit ** 2
            result += square
        return result

Optimized Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each item once
• Space: $O(1)$ → Reason: Not storing all generated numbers