Happy Number Algorithm

Problem Description

Determine if a number n is a happy number. A happy number is defined by repeatedly replacing the number by the sum of the squares of its digits until it equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Return true if n is a happy number, and false if not.

Brute Force Solution

A brute force approach would involve simulating the process as described in the problem and checking if we encounter a cycle. We can keep track of the numbers we have seen so far using a set. If we encounter a number that is already in the set, it means we are in a cycle.

Algorithm

1. Initialize a set to store the visited numbers.
2. Start a loop that continues until the number n is 1 or we find a cycle.
3. Inside the loop, calculate the sum of the squares of the digits of n.
4. If the new number is 1, return true.
5. If the new number is already in the set, return false.
6. Add the new number to the set and update n with the new number.

Code (Python)

def isHappy_brute_force(n: int) -> bool:
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        sum_of_squares = 0
        while n > 0:
            digit = n % 10
            sum_of_squares += digit ** 2
            n //= 10
        n = sum_of_squares
    return n == 1

Time Complexity: O(k), where k is the number of iterations it takes to reach 1 or a cycle.

Space Complexity: O(k), where k is the number of iterations it takes to reach 1 or a cycle, due to storing visited numbers in the set.

Optimal Solution

An optimized approach can use Floyd's cycle-finding algorithm (also known as the "tortoise and hare" algorithm) to detect cycles. Instead of storing all visited numbers in a set, we use two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the two pointers will eventually meet. If there is no cycle, both pointers will eventually reach 1.

Algorithm

1. Initialize two pointers, slow and fast, both starting at n.
2. Move slow one step at a time and fast two steps at a time.
3. If fast becomes 1, return true.
4. If slow and fast meet, return false.

Code (Python)

def isHappy(n: int) -> bool:
    def get_next(n):
        sum_of_squares = 0
        while n > 0:
            digit = n % 10
            sum_of_squares += digit ** 2
            n //= 10
        return sum_of_squares

    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

Time Complexity: O(log n). The number of times the algorithm iterates is logarithmic with respect to n because, on average, the number of digits reduces with each sum of square computation.

Space Complexity: O(1). The algorithm uses constant extra space.

Edge Cases

• n = 1: Should return true immediately.
• n = 2: Should return false as it enters a cycle.
• n is a large number: The algorithm should handle large numbers without overflowing.