Finding Happy Number

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.

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: 
    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) ]