Question

LeetCode Link | 202. Happy Number | 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.

Constrains

  • 1 <= n <= 2^31 - 1

Examples

Example 1

Input: n = 19
Output: true

Explanation:

  1. 12 + 92 = 82
  2. 82 + 22 = 68
  3. 62 + 82 = 100
  4. 12 + 02 + 02 = 1

Example 2

Input: n = 2
Output: false

Solution Approach

Method: Unordered Set / Hash Table

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This question might looks like a math question, but it actually not!

In question’s description, it says a non-happy number will have a infinite loop on calculating sum. This means during sum calculations, sum will have same value at some time which is the key for the solution.

We could use hash method (unordered_set) to determine if this sum value apears twice, if so, it return false immediately, otherwise keep calculating sum util it reach 1.

Code

  • Time complexity: O(logn)
  • Space complexity: O(logn)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
function isHappy(n: number): boolean {
    function calcSum(val: number): number {
        return String(val).split("").reduce((pre, cur) => (pre + Number(cur) * Number(cur)), 0);
    }

    let storeSet: Set<number> = new Set();
    while (n !== 1 && !storeSet.has(n)) {
        storeSet.add(n);
        n = calcSum(n);
    }
    return n === 1;
};

Conclusion

When dealing with this type of question, find the key of solution first. When we need to quickly determine whether an element appears in a set, we should consider using hash methods.