202. Happy Number
On This Page
In this problem, we are given a number
n. We have to determine whether this number is a “happy” number or not. 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.
- 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.
A naive solution would be to follow the process as stated in the problem description and use a data structure such as a set to check for repetitions indicating a cycle. If during the process, the number becomes 1, we can conclude that the number is happy. However, if we encounter a number that was already visited, it means we are stuck in a cycle, and the number is not happy.
- We calculate the sum of squares of the digits of n in each iteration, and check if this sum is 1 or a number we’ve seen before.
- If it’s 1, we return true.
- If it’s a number we’ve seen before, we return false, as this means we’re in an endless loop.
Hints & Tips
However, continuously checking if a number was already visited can be costly in terms of time complexity. A more efficient way to detect cycles is to use the Floyd Cycle detection algorithm (also known as the “Tortoise and the Hare” algorithm).
This algorithm allows us to detect a cycle in the sequence without having to store all previously seen numbers, making it more efficient in terms of space usage.
Floyd Cycle detection algorithm works by moving two pointers at different speeds - a slow pointer (tortoise) and a fast pointer (hare). If there is a cycle, the fast pointer will eventually meet the slow pointer again.
- Initialize two pointers slow and fast as
- slow with the sum of the squares of its digits,
- and fast with the sum of squares of the next number in the sequence.
- If fast becomes 1, return
nis a happy number.
- If slow meets fast and the number is not 1, return
nis not a happy number as we have detected a cycle.
def isHappy(n): def get_next(num): # get the next number in the sequence total_sum = 0 while num > 0: # get the last digit of the number and the remaining part num, digit = divmod(num, 10) total_sum += digit ** 2 return total_sum slow = n fast = get_next(n) visited = set() while fast != 1 and slow != fast: slow = get_next(slow) fast = get_next(get_next(fast)) visited.add(slow) if fast in visited: break return fast == 1
In this solution, the function
get_next(n) is used to get the next number in the sequence by replacing
n with the sum of the squares of its digits.
fast equals 1 or
slow catches up to
fast, we continue moving
slow one step at a time and
fast two steps at a time. If
fast equals 1 at the end of the loop,
n is a happy number.