Hide sidebar
leetcode/DSA courseSystem Design

Happy Number

Hashing
EasyLeetCode #202
20 min

Problem Statement

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.

Example

Example 1:

Input: n = 19

Output: true

Solution (Hash Set)

We can use a hash set to detect cycles. As we compute the sum of squares, we store each new number in the set. If we encounter a number that's already in the set, we know we're in a cycle.

Algorithm Steps

  • Create a hash set to store numbers we've seen.
  • In a loop, while the current number is not in the set:
  • Add the current number to the set.
  • Calculate the sum of the squares of its digits to get the next number.
  • If the number becomes 1, it's a happy number, so return `true`.
  • If the loop terminates, it means we've entered a cycle, so return `false`.

Current Number

19

Visited Set

19
Current number is 19. Adding to visited set.
Happy Number Solution

class Solution:
    def isHappy(self, n: int) -> bool:
        visit = set()
        
        while n not in visit:
            visit.add(n)
            n = self.sumOfSquares(n)
            
            if n == 1:
                return True
        
        return False
        
    def sumOfSquares(self, n: int) -> int:
        output = 0
        while n:
            digit = n % 10
            digit = digit ** 2
            output += digit
            n = n // 10
        return output