Leetcode – Happy Number Solution in Python

In the realm of programming problems, some captivate us with their mathematical allure and seemingly simple nature. The Happy Number problem on LeetCode is one such problem. It’s a delightful puzzle that incorporates number theory and cycle detection. In this extensive article, we will thoroughly explore the Happy Number problem, dissect multiple strategies for solving it, and implement these solutions in Python.

Problem Statement

The Happy Number problem is listed as problem number 202 on LeetCode. Here’s the problem statement:

Write an algorithm to determine if a number n is happy.

A happy number is a number which eventually reaches 1 when replaced by the sum of the square of each digit.

For example, 19 is a happy number because:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 1:
Input: n = 19
Output: true
Explanation:
As explained above, 19 is a happy number.

Example 2:
Input: n = 2
Output: false

Understanding the Problem

In this problem, we are given a positive integer n. We need to determine if it’s a “happy number”. A number is considered happy if, by repeatedly replacing the number with the sum of the squares of its digits, we eventually reach 1.

For example, let’s take the number 19: 1² + 9² = 82 8² + 2² = 68 6² + 8² = 100 1² + 0² + 0² = 1 Since we reached 1, 19 is a happy number.

Approach 1: Naive Approach

A naive approach is to simply simulate the process. We can continuously replace the number with the sum of the squares of its digits until it becomes 1, in which case we return True. However, we need a mechanism to recognize when we are stuck in a cycle that doesn’t include 1, so we don’t end up in an infinite loop.

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

This approach has a time complexity that depends on the number of iterations needed to reach 1 or detect a cycle. The space complexity is also dependent on the number of unique numbers encountered.

Approach 2: Floyd’s Tortoise and Hare (Cycle Detection)

One way to improve the space complexity of the solution is to detect cycles using Floyd’s Tortoise and Hare algorithm. This algorithm is used to detect cycles in sequences.

We can think of our number transformations as generating a sequence of numbers. If there is a cycle, then the sequence will be infinite. We can keep two pointers, one (the hare) moving twice as fast as the other (the tortoise). If there is a cycle, the hare will eventually meet the tortoise.

def get_next(n):
    return sum(int(digit) ** 2 for digit in str(n))

def isHappy(n):
    tortoise = n
    hare = get_next(n)
    while hare != 1 and hare != tortoise:
        tortoise = get_next(tortoise)
        hare = get_next(get_next(hare))
    return hare == 1

This approach has a similar time complexity to the first approach but a constant space complexity, O(1).

Mathematical Insight

It’s worth mentioning that for the Happy Number problem, the sequence will always enter a cycle – it will either enter the happy cycle [1], or a cycle that doesn’t contain 1.

Conclusion

The Happy Number problem serves as an engaging introduction to the world of cycle detection and number theory. Through the different approaches we’ve explored, we can see how algorithmic thinking and mathematical insights can help in crafting efficient solutions to seemingly simple problems. Additionally, the techniques applied in solving this problem, such as cycle detection, have far-reaching applications in computer science and other fields.