Happy Number
(#202), Easy
Category: Math, Hash Table, Two Pointer
Problem Statement
Write an algorithm to determine if a number `n` is a happy number. A happy number is a number defined by the following process: 1. Starting with any positive integer, 2. Replace the number with the sum of the squares of its digits, 3. Repeat the process until the number equals 1 (where it will stay), 4. Or it loops endlessly in a cycle that does not include 1. If it ends in 1, return `true`. Otherwise, return `false`.
Examples
Input: n = 19
Output: true
Explanation: 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1 → returns true.
Input: n = 2
Output: false
Explanation: Goes into a cycle and never reaches 1 → returns false.
Approach
Approach: Using Set to Detect Cycle
- Initialize an empty Set to store previously seen numbers.
- Loop while the number is not equal to 1.
- If the number is already in the Set, it means a cycle is detected → return false.
- Otherwise, add the number to the Set.
- Compute the sum of the squares of its digits.
- Replace the number with this sum and repeat.
- If number becomes 1, return true.
// 🔹 Approach: Using Set
var isHappy = function(number) {
let seenNumbers = new Set();
while (number !== 1) {
if (seenNumbers.has(number)) {
return false;
}
seenNumbers.add(number);
let current = number;
let sumOfSquares = 0;
while (current > 0) {
let digit = current % 10;
sumOfSquares += digit * digit;
current = Math.floor(current / 10);
}
number = sumOfSquares;
}
return true;
};Complexity
Time: O(log n) – processing each digit of the number at every step
Space: O(log n) – to store intermediate results in the Set