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 seen.add(n) # add the number to observed list (set) # 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.
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: prev.add(n) 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: prev.add(n) # 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) ]