202. Happy Number

Problem Statement

link: https://leetcode.com/problems/happy-number/ https://leetcode.cn/problems/happy-number/

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:

Input: n = 19 Output: true

Input: n = 2 Output: false

Solution Approach

The solution uses a set to track already seen numbers and determines if the process leads to a repetitive loop or converges to 1.

Algorithm

1. Initialization: Begin with a set to record numbers we’ve seen during the computation.
2. Square and Sum: For each digit of the current number, square it and sum all squares to produce a new number.
3. Check for Repetition: If this new number is already in our set, return false (since it’s starting a loop). If the new number is 1, return true. Otherwise, continue the process with the new number.

Implement

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

    
    

Twitter  facebook  Email