202. Happy Number

LeetCode Link (opens in a new tab)

Hash Table

Description

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 cases

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^{31} - 1}$

Approach

각 자리수의 제곱의 합을 반복하여 그 합이 1이 되는 경우가 나오면 happy number라고 한다.
1이 나오지 않고 무한 루프에 빠지면 happy number가 아니기 때문에 false를 반환하면 된다.
자리수의 제곱의 합을 구하고 1인지 확인하는건 아주 간단한데 이 문제의 핵심은 무한루프에 빠진다는걸 어떻게 알 수 있냐는 것이다.
무한루프에 빠지는 경우는 자리수의 제곱의 합이 이전에 나왔던 값이 나오는 경우이다. 이 경우 cycle이 형성되기 때문에 이 cycle을 무한반복하게 된다.
즉 hash table을 하나 만들어서 자리수의 제곱의 합이 나올 때마다 hash table에 저장하고 이미 나왔던 값이 나오면 false를 반환하면 된다.

Solution Code

var isHappy = function(n) {
    const map = new Map()
    const sumOfSquaresOfDigits = (num) => num.toString().split('').reduce((acc, cur) => Math.pow(Number(cur), 2) + acc, 0)
 
    while (n !== 1) {
        n = sumOfSquaresOfDigits(n)
        if (map.has(n)) {
            return false
        }
        map.set(n, true)
    }
 
    return true
};

Complexity

• time complexity : O(n)
• space complexity : O(n)