202. Happy Number

Problem Statement in English

You’re given a number n. You need to determine if the number is a happy number.

A number is called a happy number if the sum of the squares of its digits eventually leads to 1.

Approach

We can use a set to keep track of the numbers we have seen. If we see a number that we have already seen, we can return False. If we reach 1, we can return True.

Apart from that it’s just implementing the digit squaring and summing logic.

Solution in Python

class Solution:
    def isHappy(self, n: int) -> bool:
        s = 0
        seen = set()

        while n > 3:
            if n in seen:
                return False
            seen.add(n)
            s = 0
            while n > 0:
                units = n % 10
                n //= 10
                s += units**2

            n = s

        if n == 1:
            return True
        return False

Complexity

• Time: $O(logn)$
  where $n$ is the number given to us, since a number $n$ with have at most $logn$ digits.
  

• Space: $O(logn)$
  Since we store all the numbers we’ve seen

Mistakes I Made

I forgot to add the set to keep track of the numbers we’ve seen.

And we are done.