202.Happy_Number(Easy).md

202. Happy Number (Easy)

Date and Time: Jan 9, 2025, 22:00 (EST)

Link: https://leetcode.com/problems/happy-number

Question:

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.

• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

• Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
$1^2 + 9^2 = 82$
$8^2 + 2^2 = 68$
$6^2 + 8^2 = 100$
$1^2 + 0^2 + 0^2 = 1$

Example 2:

Input: n = 2
Output: false

Constraints:

• $1 <= n <= 2^{31} - 1$

Walk-through:

Hashmap:
We use set() to detect when there is a repeated number exists in the set() so we know this is not possible to reach 1. Each time, before getting the new n, add the previous n into set() first.

Slow-fast Approach:
Use slow, fast ptrs to keep track of the current number, by the property of this algorithm, if there is a loop, we will be able to detect it, when slow == fast, so we will break the while loop and check if slow == 1. Otherwise, we check fast == 1 in the while loop to make sure we break early when fast == 1.

Hashmap Solution:

class Solution:
    def isHappy(self, n: int) -> bool:
        # Use set() to detect when there is a cycle
        
        # TC: O(n), n is how many numbers until repeated, SC: O(n)
        visited = set()
        while n not in visited:
            visited.add(n)
            tmp = 0
            while n:
                tmp += (n % 10) ** 2
                n //= 10
            n = tmp
            if n == 1:
                return True
        return False

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Slow-fast Approach:

class Solution:
    def isHappy(self, n: int) -> bool:
        # Use slow-fast approach to detect if loop exists
        # Recursively call on slow, fast to update ptrs

        # TC: O(n), n is total numbers needed SC: O(1)
        def number(i):
            tmp = 0
            while i:
                tmp += (i % 10) ** 2
                i //= 10
            return tmp

        slow, fast = number(n), number(number(n))
        while slow != fast:
            # Check if fast == 1, since it aheads of slow ptr
            if fast == 1:
                return True
            slow, fast = number(slow), number(number(fast))
        return slow == 1

Time Complexity: $O(n)$
Space Complexity: $O(1)$