π‘ Problem Formulation: A “happy number” is defined as a number which eventually reaches 1 when replaced by the sum of the square of each digit. If this process results in an endless cycle of numbers which does not include 1, then the number is considered “unhappy”. Our task is to implement a Python program to determine if a given number is happy. For example, input 19 should result in output “True” since 12 + 92 = 82, 82 + 22 = 68, 62 + 82 = 100, and 12 + 02 + 02 = 1, thus completing our sequence at 1.
Method 1: Using a Loop and Hash Set
This method involves using a while loop to iterate through the process of calculating the sum of the squares of digits. A hash set is used to store the numbers that have been seen. If the number is repeated, it signs an endless loop and thus not a happy number. If 1 is reached, the number is happy.
Here’s an example:
def is_happy(n): seen_numbers = set() while n not in seen_numbers: seen_numbers.add(n) n = sum(int(digit)**2 for digit in str(n)) if n == 1: return True return False # Checking if 19 is a happy number print(is_happy(19))
Output: True
This code snippet defines a function is_happy()
that takes an integer n
and returns True
if it’s a happy number, otherwise False
. It uses a set to keep track of all the numbers it has already seen to avoid loops, and it keeps iterating until it finds 1 or detects a loop.
Method 2: The Slow-Fast Pointer Technique
Method 2 employs the slow-fast pointer approach, also known as Floyd’s cycle-finding algorithm, to detect cycles within the sequence of calculations. If the slow and fast pointers meet, a cycle is detected and the number isn’t happy.
Here’s an example:
def get_next(number): return sum(int(ch) ** 2 for ch in str(number)) def is_happy_floyd(number): slow = number fast = get_next(number) while fast != 1 and slow != fast: slow = get_next(slow) fast = get_next(get_next(fast)) return fast == 1 print(is_happy_floyd(19))
Output: True
This code snippet uses two pointers moving at different speeds to traverse the sequence generated by the sum of squares of digits. If both pointers meet, and the fast pointer is not 1, we have a cycle and the number isn’t happy.
Method 3: Recursive Approach
In this method, a recursive function is used to simulate the process of finding a happy number. A base case is included to stop the recursion if a cycle is detected or if 1 is reached.
Here’s an example:
def is_happy_recursive(n, seen=None): if seen is None: seen = set() if n == 1: return True if n in seen: return False seen.add(n) return is_happy_recursive(sum(int(x)**2 for x in str(n)), seen) print(is_happy_recursive(19))
Output: True
The is_happy_recursive()
function iterates over the number, summing the squares of its digits, in a recursive manner. It maintains a set to track visited numbers to detect cycles.
Method 4: Using Mathematics
This method explores the fact that all unhappy numbers follow a pattern where they eventually fall into the cycle 4, 16, 37, 58, 89, 145, 42, 20, and then 4 again. We can use this knowledge to determine if a number is happy or not.
Here’s an example:
def is_happy_math(n): while n > 1 and n != 4: n = sum(int(i) ** 2 for i in str(n)) return n == 1 print(is_happy_math(19))
Output: True
The is_happy_math()
function repeatedly replaces the number with the sum of the squares of its digits. The loop stops when the number is reduced to either 1 (happy) or 4 (unhappy, beginning of the cycle).
Bonus One-Liner Method 5: The Pythonic Way
This method uses Python’s expressive power to encompass the whole happy number checking algorithm in a single line. It combines a lambda function, a generator expression, and the any() built-in function.
Here’s an example:
is_happy_oneliner = lambda n, seen: n == 1 or n not in seen and not is_happy_oneliner(sum(int(x)**2 for x in str(n)), seen | {n}) print(is_happy_oneliner(19, set()))
Output: True
This one-liner uses a lambda function that includes a recursive call to itself. It checks if the number has reached 1 or not yet been seen. It updates the set of seen numbers using set union.
Summary/Discussion
- Method 1: Loop and Hash Set. Strengths are simplicity and clear logic. Weakness is potential space complexity due to storage of seen numbers.
- Method 2: Slow-Fast Pointer Technique. Strength is the efficient detection of cycles without auxiliary space. Weakness is the less intuitive approach.
- Method 3: Recursive Approach. Strength is simplifying code structure; however, stack overflow could be a weakness with a very unlucky number.
- Method 4: Using Mathematics. Strength is very fast for small numbers. Weakness is relying on the precomputed cycle which may not be easily understandable.
- Bonus Method 5: Pythonic One-Liner. Strengths are brevity and elegant use of Python’s features. Weaknesses are reduced readability and debugging difficulty.