Search
• Mani Abedini

# Finding Happy Number

Updated: Jul 11, 2020

This coding exercise is part of "30-day-leetcoding-challenge" campaign.

The link to the challenge is here: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3284/

In a nutshell, Happy number is a number that eventually reaches to value "1" by replacing the number with the sum of the squared of its digits. Unhappy number on the other hand, is a number that never reaches to value "1" and stays in an infinite loop forever.

For example, 19 is a happy number:

But 4 is not Happy number:

...

Solution 1: Recursion

My first impression was, the problem is a typical recursive problem. However, to escape from infinite loop, we need a memorisation mechanism; by defining "Seen", a set of previous observed values.

My recursive solution is:

def SquareSumDigits(nom): # calculate the square sum of all digits
sumDig =0
while nom > 0:
sumDig += (nom%10) **2
nom=nom//10
return sumDig
 #recursive function
def isHappy (n, seen):
if n in seen:  # if the number is already seen
return n

# call the function to run on squared sum of the digits
return isHappy( SquareSumDigits(n), seen)

#main code
prev = set()
return isHappy(n, prev) ==1               

Solution 2: Non-Recursion

However, recursion is expensive. It is much cheaper in terms of execution time and memory to solve it with iterative loop. However, in terms of speed complexity both are O(mn) when m is the length of generated numbers and n is the max number of digits.

Here is my code without recursive, which achieved a good score in terms of speed (above 99% submissions) but not a good score in terms of used memory (beats 34%).

def SquareSumDigits(nom): # calculate the square sum of digits
sumDig =0
while nom > 0:
sumDig += (nom%10) **2
nom=nom//10
return sumDig
prev = set() # a list of observed numbers

while n != 1 and n not in prev:
n = sumDigits(n)

# the loop ends either we reach 1 or infinite loop is detected
if n == 1:
return True
else:
return False                          

Solution 3: Simpler Digit extraction

Further Pythonizing the code, here is the final code, faster and with less memory usage:

prev = set()# a list of observed numbers

while n != 1 and n not in prev:
# Split the number into digits then Squared
n = sum (map(lambda x: int(x)**2, str(n)))

# the loop ends either we reach 1 or infinite loop is detected
return n ==1 

Interesting key learning points:

• Searching in a set is fast ( O(1) ) because implemented by hash-table.

• (nom%10) **2 is faster than (nom%10) *(nom%10)

• There is a maximum recursion depth that can limit recursive approach.

• Converting the number to string then iterating over characters to extract digits was faster and much simpler in Python:

        [ int(d) for d in str(N) ]