Happy Number easy

Problem Statement

Write an algorithm to determine if a number 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 (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 numbers.

Example 1:

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

Example 2:

Input: n = 2 Output: false Explanation: 2² = 4 4² = 16 1² + 6² = 37 3² + 7² = 58 5² + 8² = 89 8² + 9² = 145 1² + 4² + 5² = 42 4² + 2² = 20 2² + 0² = 4 ...

Steps:

1. Initialize a set: Create a seen set to store the numbers encountered during the process. This set will help detect cycles.
2. Iterate until 1 or cycle is detected: While the number n is not 1 and not in the seen set:
   • Add n to the seen set.
   • Calculate the sum of squares of digits of n.
   • Update n with the calculated sum.
3. Return the result: If n is 1, return True (happy number). Otherwise, return False (unhappy number or cycle detected).

Explanation:

The algorithm uses a set (seen) to efficiently detect cycles. If a number repeats during the process, it means the process will loop endlessly without reaching 1, indicating an unhappy number. The algorithm terminates when either 1 is reached (happy number) or a cycle is detected (unhappy number).

Code:

def isHappy(n: int) -> bool:
    seen = set()  # Use a set to track seen numbers

    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(digit)**2 for digit in str(n))

    return n == 1

Complexity:

• Time Complexity: O(log n). The number of iterations is generally logarithmic because the number tends to decrease in size with each iteration. In the worst case (a very long cycle), it could be higher, but it's bounded by the maximum number of unique sums possible.
• Space Complexity: O(log n). The space used by the seen set is proportional to the number of iterations, which is again generally logarithmic. In the worst case, it would be proportional to the length of a potential cycle.