Introduction

A Happy Number is a number that eventually reaches 1 when replaced repeatedly by the sum of the squares of its digits.

If the process enters a cycle that does not include 1, the number is not a happy number.

This problem helps in understanding:

  • Digit extraction
  • Hashing
  • Cycle detection
  • Set usage
  • Number manipulation

Problem Statement

Given an integer n, determine whether it is a happy number.

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually results in 1.

Return true if the number is happy; otherwise, return false.

Example

Input:
n = 19

Output:
true

Explanation:
19 → 1² + 9²
   → 1 + 81
   → 82
   → 8² + 2²
   → 64 + 4
   → 68
   → 6² + 8²
   → 36 + 64
   → 100
   → 1² + 0² + 0²
   → 1
Therefore, 19 is a happy number. 

Input:n = 2

Output:
false

Explanation:
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
The sequence enters a cycle and never reaches 1.
Therefore, 2 is not a happy number.

Constraints

  • 1 ≤ n ≤ 2³¹ - 1

Approach 1: Brute Force

Explanation

The brute force approach repeatedly calculates the sum of the squares of the digits.

To detect whether the process is stuck in a cycle, we can continue generating values until either:

  • The value becomes 1, or
  • A known repeating cycle is reached.

For this problem, the cycle can be detected by checking whether the sequence reaches 4.

Steps

  1. Calculate the sum of the squares of the digits.
  2. Replace the number with this sum.
  3. Repeat the process.
  4. If the number becomes 1, return true.
  5. If the number becomes 4, return false.

Dry Run

Input:n = 19

19 → 82
82 → 68
68 → 100
100 → 1

The number reaches 1.

Final Result:
true

Brute Force Code

Complexity Analysis

Time Complexity: O(log n) per digit-sum calculation, with a bounded number of iterations after the value becomes small.

Space Complexity: O(1)

Only a constant amount of extra space is used.

Approach 2: Optimized Solution

Explanation

The optimized approach uses a Set to detect repeated values.

Instead of relying on the known cycle value 4, we store every number produced during the process.

If a number appears again, a cycle has been detected.

Steps

  1. Create an empty Set.
  2. While n is not 1:
    • If n already exists in the Set, a cycle is detected.
    • Add n to the Set.
    • Replace n with the sum of the squares of its digits.
  3. Return true if n becomes 1.

Dry Run

Input:n = 2

Start:
Set = {}

2 → add to Set
Set = {2}

4 → add to Set
Set = {2, 4}

16 → add to Set
Set = {2, 4, 16}

37 → add to Set
Set = {2, 4, 16, 37}
...
20 → add to Set
4 → already exists in Set

Cycle detected.

Final Result:
false

Optimized Code

Complexity Analysis

Time Complexity: O(log n) per digit-sum calculation, with a bounded number of generated states.

Space Complexity: O(log n)

The Set stores previously encountered values.

Edge Cases

  1. n = 1: It is already a happy number.
  2. n = 19: Eventually reaches 1.
  3. n = 2: Enters a cycle and is not happy.
  4. Single-digit number: Check whether repeated digit-square calculation reaches 1.
  5. Repeated value: Indicates that a cycle has been detected.

Why This Problem is Important

This problem helps in understanding:

  1. Hash Sets
  2. Cycle detection
  3. Digit manipulation
  4. Modulo and division
  5. Repeated-state problems

Real-World Applications

Cycle detection concepts are useful in:

  1. State-based algorithms
  2. Graph and linked-list problems
  3. Repeated process detection
  4. Caching previously visited states
  5. Algorithm optimization

Common Mistakes

  1. Forgetting to detect cycles.
  2. Calculating the digit square incorrectly.
  3. Forgetting to update the number after each iteration.
  4. Confusing the sum of digits with the sum of squared digits.
  5. Using an infinite loop without a cycle-detection condition.

Interview Tips

The key observation is that the sequence can repeat.

A common solution is to use a Set to remember previously seen values.

If the same value appears again, the process is stuck in a cycle and the number is not happy.

Related Questions

  1. Introduction to Set
  2. Introduction to Map
  3. Count Digits
  4. Reverse Number
  5. Palindrome Number

Final Takeaway

The Happy Number problem combines digit manipulation with cycle detection.

The brute force approach can use the known cycle condition, while the optimized hashing approach uses a Set to detect repeated states. This makes the problem a useful introduction to applying hashing techniques to number-based problems.