LeetCode202 Happy Number

Author: Stefan Su
Create time: 2022-10-31 11:29:09
Location: New York City, NY, USA

Description Easy

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 1

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2

Input: n = 2
Output: false

Constrains

• 1 <= n <= 2³¹ - 1

Analysis

Honestly, this problem has only a while loop, but knowing the fact is important, that’s, a number is either a happy number or not. It means if these square operations can have repeated square result, it cannot be a happy number. Otherwise, it will continue until resulting in 1. We use unordered hash map to solve this problem. Remember, be familiar with a function that can sum up each digit in a number.

Solution

• unordered hash map version

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """

        # define a function to sum up the square of each digit in the number
        # get familiar with this function
        def sum_happy(num):
            total = 0

            while num:
                total += (num % 10) ** 2
                num //= 10
            
            return total
        
        record = set()

        while True:
            n = sum_happy(n)
            if n == 1:
                return True
            
            # if n in record, then it is not a happy number
            # BUT, how to prove a number is either a happy number or not
            if n in record:
                return False
            else:
                record.add(n)

Hopefully, this blog can inspire you when solving LeetCode202. For any questions, please comment below.