Happy Number

Problem

https://leetcode.com/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 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

Constraints:

• 1 <= n <= 2:sup:`31`- 1

Pattern

Hash Table, Math, Two Pointers

Approaches

Hash Set

Explanation

For 1000 iterations, sum the squares of each digit. If the sum is 1, return True. If the sum has been seen before, return False. Otherwise, continue.

Code

def isHappy(n: int) -> bool:
    """Checks if a number is happy."""
    old_n = set()
    for i in range(1000):
        if n == 1:
            return True
        elif n in old_n:
            return False
        else:
            old_n.add(n)
            n = sum_of_square_of_digits(n)
    return True


def sum_of_square_of_digits(n):
    s = 0
    for digit in str(n):
        s += int(digit) ** 2
    return s

Test

>>> from happy_number__hash_set import isHappy
>>> isHappy(19)
True
>>> isHappy(2)
False

Complexity

\(k\) is the number of iterations

Measure	Complexity	Notes
Time	\(O(k)\)	each iteration requires summing the squares of the digits
Auxiliary Space	\(O(k)\)	set stores at most \(k\) key-value pairs

happy_number__hash_set.isHappy(n: int) → bool

Checks if a number is happy.

happy_number__hash_set.sum_of_square_of_digits(n)