Leetcode: Happy number

05 Oct 2022 by Friedrich Ewald · 2 min read

Write an algorithm to determine if a number n is happy. 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. Return true if n is a happy number, and false if not.

For example, the number 19 is divided into 1^2 and 9^2, then added together as 82, then divided again, etc. After some iterations this reaches 100 which is 1^2 + 0^2 + 0^2 = 1. On the other hand, 2 keeps ever incremententing. The programming aspect is relatively easy to solve in Python when converting the types to a string and then converting the string to a list. When solving this problem I recommend to first focus on the loop that eventually reaches to 100 and implement the valid case. Once this is done, one can print out the numbers that get visited when using the same algorithm with 2. It becomes obvious that the chain of visited numbers looks something like this: 2 -> 4 -> ... -> 4. With this observation we know that invalid numbers have loops and we can use a set to detect if we encounter a loop.

class Solution:
  def isHappy(self, n: int) -> bool:
    seen = set()
    n = [*str(n)]
    while n != ['1']:
      s = 0
      for i in n:
        s += int(i) ** 2
      if s in seen:
        return False
      seen.add(s)
      
      n = [*str(s)]
    return True


if __name__ == '__main__':
  s = Solution().isHappy
  print(s(19), True)
  print(s(2), False)

Runtime: 71 ms, faster than 14.54% of Python3 online submissions for Happy Number. Memory Usage: 13.9 MB, less than 14.75% of Python3 online submissions for Happy Number.

---