Happy Number Leetcode Problem 202 [Python Solution]

Let’s do some more Leetcode, continuing with the Happy Number Leetcode problem; discuss, explore, understand and provide you with an efficient Python solution.

We’ll explore what makes a number “happy” and provide you with an efficient Python solution to determine if a number is indeed a happy number.

So, whether you’re a beginner or an experienced coder, we’ve got you covered.

Let’s get started!

Problem Overview

The Happy Number problem presents us with an interesting concept.

We are given a positive integer n, and our goal is to determine whether it is a happy number.

But what exactly is a happy number?

A happy number is defined by the following process:

1. Start with any positive integer.
2. Replace the number by the sum of the squares of its digits.
3. Repeat the process until the number equals 1 (where it will stay), or it enters an endless cycle that doesn’t include 1. To clarify, if the process eventually reaches the number 1, the number is considered happy, and we should return True.

If the process never reaches 1 and gets stuck in an endless loop, the number is not happy, and we should return False.

Let’s illustrate this with an example:

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

In this case, the process led to 1, which means that 19 is a happy number.

Example 2:

Input: n = 2
Output: False

In this example, the process does not lead to 1 but instead goes in a cycle: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> …

As you can see, it never reaches 1. Thus, the number 2 is not a happy number.

Constraints:

• 1 <= n <= 2^31 – 1

Now that we have a clear understanding of the problem, let’s explore the Python solutions.

Understanding Happy Number Constraints

Before we dive into the code, let’s consider the constraints of the Happy Number problem.

The input number n can range from 1 to 2^31 – 1, which means we might need an efficient algorithm to handle larger inputs.

Additionally, we need to be careful about potential endless loops, so our algorithm must address this concern.

Happy Number LeetCode Problem Solution

Now, let’s move on to the solution.

We’ll present both a brute-force approach and an efficient approach to solving the Happy Number problem.

1. Bruteforce Approach

Our first approach to solving this problem is a brute-force method.

We will implement a loop that repeatedly calculates the sum of the squares of the digits of n until n becomes 1 or enters a cycle.

We will use a set to keep track of the numbers we’ve encountered during the process.

If we encounter a number that we’ve seen before (indicating a cycle), we return False.

If we reach 1, we return True.

Here’s the Python code for this approach:

def isHappy(self, n: int) -> bool:
    visited = set()  # To keep track of visited numbers
    while n != 1:
        if n in visited:
            return False  # We've entered a cycle
        visited.add(n)  # Add the current number to the set
        n = self.sumSquareDigits(n)  # Calculate the sum of squares
    return True

def sumSquareDigits(self, n):
    output = 0
    while n:
        output += (n % 10) ** 2
        n = n // 10
    return output

In this code, sumSquareDigits is a helper function to calculate the sum of squares of the digits of a number.

2. Efficient Approach with Floyd’s Cycle Detection Algorithm

While the brute-force approach is correct, it’s not the most efficient solution.

There’s a clever way to approach this problem using Floyd’s Cycle Detection Algorithm, also known as the “tortoise and hare” algorithm.

This algorithm is used to detect cycles in a linked list, and it’s applicable to our problem because we can treat the process as a linked list, with each number leading to the next in the sequence.

Here’s the Python code for the efficient approach:

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

        while slow != fast:
            fast = self.sumSquareDigits(fast)
            fast = self.sumSquareDigits(fast)
            slow = self.sumSquareDigits(slow)

        return True if fast == 1 else False  

    def sumSquareDigits(self, n):
        output = 0
        while n:
            output += (n % 10) ** 2
            n = n // 10
        return output

In this efficient approach, we have two pointers, slow and fast, initialized with the input n.

We calculate the sum of squares of digits for both pointers.

The fast pointer moves twice as fast as the slow pointer.

If there’s a cycle, these two pointers will eventually meet at the same number.

If they meet at 1, we return True, indicating that n is a happy number.

Otherwise, we return False.

Now that we have presented both approaches, let’s discuss the time and space complexity of our solution.

Time and Space Complexity

Understanding the time and space complexity of our solution is crucial for assessing its efficiency and scalability.

Time Complexity:

In both the brute-force and efficient approaches, we are essentially traversing a sequence of numbers.

In the worst case, where n is not a happy number and enters an endless loop, the loop will continue indefinitely.

However, the fast and slow pointers in the efficient approach will eventually meet, indicating that the loop is a cycle.

Therefore, both approaches have a time complexity of O(c), where c is the length of the cycle.

Space Complexity:

The space complexity of the brute-force approach is O(c), where c is the length of the cycle.

We use a set to keep track of visited numbers, and in the worst case, this set can contain all unique numbers in the cycle.

The space complexity of the efficient approach is O(1).

We only use a constant amount of additional space to store the slow and fast pointers.

The efficient approach is preferable as it uses less space and performs similarly in terms of time complexity.

It leverages a well-known algorithm for cycle detection.

Reasoning Behind Our Approach

The problem of determining happy numbers can be approached in various ways.

We’ve presented two solutions: a straightforward brute-force approach and an efficient approach based on cycle detection.

The brute-force approach is intuitive and easy to understand.

It involves simulating the process of repeatedly calculating the sum of squares of digits until we either reach 1 (a happy number) or enter a cycle.

The use of a set allows us to detect cycles and return False when necessary.

While this approach is correct, it may not be the most efficient for large inputs.

The efficient approach, using Floyd’s Cycle Detection Algorithm

, is a clever way to tackle the problem.

By treating the process as a linked list and using two pointers, we can detect cycles with minimal additional space.

This approach is more efficient, especially for larger inputs, as it guarantees that the algorithm terminates in a reasonable time.

Choosing the efficient approach demonstrates the importance of algorithm selection in problem-solving.

It’s not just about solving a problem but solving it optimally and efficiently.

This approach showcases the power of well-established algorithms in tackling a wide range of problems.

Related Interview Questions By Company:

• Concatenation Of Array LeetCode
• Path Sum LeetCode
• Subtree Of Another Tree LeetCode

Related Interview Questions By Difficulty:

• Roman To Integer LeetCode
• Set Matrix Zeroes LeetCode
• Multiply Strings LeetCode

Conclusion

In this blog post, we’ve explored the LeetCode Problem 202 – Happy Number.

We’ve defined what a happy number is and provided an efficient Python solution using Floyd’s Cycle Detection Algorithm.

We’ve discussed the time and space complexity of our solution and highlighted the reasoning behind our approach.

If you found this guide helpful, we encourage you to experiment with the code, ask questions, and share your thoughts.

Learning to approach problems efficiently is a valuable skill for any coder, and understanding well-established algorithms can be a game-changer in your programming journey.

To further practice and test your skills, you can access the problem directly on LeetCode through the following link: Happy Number LeetCode Problem.

Thank you for joining us in this coding adventure!

Remember, the path to becoming a proficient coder is paved with problem-solving, practice, and a passion for learning.

Stay curious and keep coding!