Saltar al contenido principal

Happy Number (Magical Number)

Given an integer n, return whether or not it is a "magical" number. A magical number is an integer such that when you repeatedly replace the number with the sum of the squares of its digits, it eventually becomes one.

Note: If the process enters a cycle (repeats numbers) without reaching 1, the number is not magical.

Example(s)​

Example 1:

Input: n = 19
Output: true
Explanation:
19 → 1² + 9² = 1 + 81 = 82
82 → 8² + 2² = 64 + 4 = 68
68 → 6² + 8² = 36 + 64 = 100
100 → 1² + 0² + 0² = 1 + 0 + 0 = 1 ✓
Since we reached 1, 19 is a magical number.

Example 2:

Input: n = 22
Output: false
Explanation:
22 → 2² + 2² = 4 + 4 = 8
8 → 8² = 64
64 → 6² + 4² = 36 + 16 = 52
52 → 5² + 2² = 25 + 4 = 29
29 → 2² + 9² = 4 + 81 = 85
85 → 8² + 5² = 64 + 25 = 89
89 → 8² + 9² = 64 + 81 = 145
145 → 1² + 4² + 5² = 1 + 16 + 25 = 42
42 → 4² + 2² = 16 + 4 = 20
20 → 2² + 0² = 4 + 0 = 4
4 → 4² = 16
16 → 1² + 6² = 1 + 36 = 37
37 → 3² + 7² = 9 + 49 = 58
58 → 5² + 8² = 25 + 64 = 89 (cycle detected!)
Since we entered a cycle without reaching 1, 22 is not magical.

Example 3:

Input: n = 1
Output: true
Explanation: Already 1, so it's magical.

Example 4:

Input: n = 7
Output: true
Explanation:
7 → 7² = 49
49 → 4² + 9² = 16 + 81 = 97
97 → 9² + 7² = 81 + 49 = 130
130 → 1² + 3² + 0² = 1 + 9 + 0 = 10
10 → 1² + 0² = 1 + 0 = 1 ✓

Solution​

The solution uses a set to detect cycles:

  1. Calculate sum of squares: Helper function to compute sum of squares of digits
  2. Track seen numbers: Use a set to store numbers we've encountered
  3. Iterate: Keep calculating the next number until we reach 1 or detect a cycle
  4. Cycle detection: If we see a number we've seen before, we're in a cycle → return false
  5. Success: If we reach 1, return true

JavaScript Solution - Set Approach

/**
* Check if a number is magical (happy number)
* @param {number} n - Integer to check
* @return {boolean} - True if n is magical
*/
function isHappy(n) {
const seen = new Set();

/**
 * Calculate sum of squares of digits
 * @param {number} num - Number to process
 * @return {number} - Sum of squares of digits
 */
function getNext(num) {
  let sum = 0;
  while (num > 0) {
    const digit = num % 10;
    sum += digit * digit;
    num = Math.floor(num / 10);
  }
  return sum;
}

// Keep iterating until we reach 1 or detect a cycle
while (n !== 1 && !seen.has(n)) {
  seen.add(n);
  n = getNext(n);
}

return n === 1;
}

// Test cases
console.log('Example 1:', isHappy(19)); // true
console.log('Example 2:', isHappy(22)); // false
console.log('Example 3:', isHappy(1)); // true
console.log('Example 4:', isHappy(7)); // true
console.log('Test 5:', isHappy(2)); // false
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Floyd's Cycle Detection)​

Here's a solution using Floyd's cycle detection algorithm (two pointers) that uses O(1) space:

/**
 * Floyd's cycle detection - O(1) space
 */
function isHappyFloyd(n) {
  function getNext(num) {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  
  // Two pointers: slow and fast
  let slow = n;
  let fast = getNext(n);
  
  // Move slow one step, fast two steps
  while (fast !== 1 && slow !== fast) {
    slow = getNext(slow);
    fast = getNext(getNext(fast));
  }
  
  return fast === 1;
}

Alternative: String-Based Digit Extraction​

Here's an alternative that converts to string to extract digits:

/**
 * Alternative: String-based digit extraction
 */
function isHappyString(n) {
  const seen = new Set();
  
  function getNext(num) {
    return String(num)
      .split('')
      .reduce((sum, digit) => sum + digit * digit, 0);
  }
  
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = getNext(n);
  }
  
  return n === 1;
}

Complexity​

  • Time Complexity: O(log n) - The number of digits in n is O(log n), and we process each digit. The cycle detection adds some overhead, but in practice it's efficient.
  • Space Complexity:
    • Set approach: O(log n) - We store numbers in the set. The maximum number we can reach is bounded.
    • Floyd's approach: O(1) - Only uses two pointers, no extra space.

Approach​

The solution uses cycle detection:

  1. Calculate next number: Sum of squares of digits

    • Extract each digit using modulo and division
    • Square each digit and sum them

  2. Detect cycles: Two approaches

    • Set approach: Track all seen numbers in a set
    • Floyd's cycle detection: Use two pointers (slow and fast)

  3. Termination conditions:

    • Success: If we reach 1, return true
    • Cycle: If we see a number we've seen before, return false

Key Insights​

  • Cycle detection is crucial: Without it, we'd loop infinitely
  • All cycles contain 4: Interestingly, all unhappy numbers eventually reach 4
  • Bounded values: The sum of squares of digits is always less than the original number (for numbers > 81)
  • Floyd's algorithm: More space-efficient but slightly more complex
  • Digit extraction: Can use modulo/division or string conversion

Step-by-Step Example​

Let's trace through Example 1: n = 19

Initial: n = 19, seen = {}

Step 1: n = 19 (not 1, not in seen)
  seen.add(19) → seen = {19}
  getNext(19):
    digits: 1, 9
    sum = 1² + 9² = 1 + 81 = 82
  n = 82

Step 2: n = 82 (not 1, not in seen)
  seen.add(82) → seen = {19, 82}
  getNext(82):
    digits: 8, 2
    sum = 8² + 2² = 64 + 4 = 68
  n = 68

Step 3: n = 68 (not 1, not in seen)
  seen.add(68) → seen = {19, 82, 68}
  getNext(68):
    digits: 6, 8
    sum = 6² + 8² = 36 + 64 = 100
  n = 100

Step 4: n = 100 (not 1, not in seen)
  seen.add(100) → seen = {19, 82, 68, 100}
  getNext(100):
    digits: 1, 0, 0
    sum = 1² + 0² + 0² = 1 + 0 + 0 = 1
  n = 1

Step 5: n = 1
  Return true (n === 1)

Mathematical Insight​

Interesting fact: All unhappy numbers eventually enter a cycle that includes 4:

  • 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle)

So we could optimize by checking if we reach 4:

while (n !== 1 && n !== 4) {
  n = getNext(n);
}
return n === 1;

However, this is less general and the set approach is clearer.

Edge Cases​

  • n = 1: Already magical, return true immediately
  • n = 0: Not magical (0 → 0, cycle)
  • Single digit: Works correctly
  • Large numbers: Eventually reduces to smaller numbers
  • Negative numbers: Typically not considered (but could handle by taking absolute value)

Optimization: Hardcoded Cycle Detection​

Since we know all cycles contain 4, we can optimize:

/**
 * Optimized: Check for 4 instead of using a set
 */
function isHappyOptimized(n) {
  function getNext(num) {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  
  // All unhappy numbers eventually reach 4
  while (n !== 1 && n !== 4) {
    n = getNext(n);
  }
  
  return n === 1;
}
  • Add Digits: Repeatedly add digits until single digit
  • Ugly Number: Check if number has only certain prime factors
  • Perfect Number: Check if number equals sum of its divisors
  • Self Dividing Numbers: Check if number is divisible by all its digits

Takeaways​

  • Cycle detection is essential for this problem
  • Set approach is simple and clear
  • Floyd's algorithm saves space (O(1) vs O(log n))
  • All cycles contain 4 - useful optimization
  • Digit extraction can be done with modulo/division or string conversion
  • Mathematical insight helps optimize the solution