Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Return true if n is a happy number, and false if not.
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 <= 231 - 1Problem Overview: You are given an integer n. Repeatedly replace the number with the sum of the squares of its digits. If the process eventually reaches 1, the number is considered a happy number. If it falls into a repeating cycle that never reaches 1, it is not.
Approach 1: Using HashSet to Detect Cycles (Time: O(log n), Space: O(log n))
This approach simulates the process directly and tracks previously seen numbers using a hash set. For each iteration, compute the sum of the squares of the digits of the current number. If the result becomes 1, the number is happy. If you encounter a value that already exists in the set, a cycle has formed and the sequence will never reach 1. The key insight is that unhappy numbers always enter a loop (for example, 4 → 16 → 37 → ... → 4). Hash lookups allow constant-time cycle detection, making the simulation efficient. This approach relies on a hash table to remember visited states and works well for explaining the logic during interviews.
Approach 2: Floyd's Cycle-Finding Algorithm (Time: O(log n), Space: O(1))
Instead of storing visited values, you can detect the cycle using the classic fast and slow pointer technique. Treat each transformation as a step in a sequence: next(n) computes the sum of squares of digits. Maintain two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps (next(next(n))). If the number is happy, both pointers eventually reach 1. If the sequence contains a cycle, the two pointers will meet at some value inside the loop. This technique is widely used in linked list cycle detection and fits well here because the transformation defines a deterministic sequence. It avoids extra memory and demonstrates knowledge of the two pointers pattern combined with basic math operations.
Recommended for interviews: Start with the HashSet approach because it clearly demonstrates the idea of detecting repeated states in a sequence. Once the cycle concept is clear, optimize the solution using Floyd's cycle detection to reduce space to O(1). Interviewers typically expect the cycle insight; showing both approaches signals strong problem-solving depth.
The idea is to use a HashSet to track all numbers we've seen so far. If we encounter a number that we've seen before, it means we're in a cycle and the number is not happy. We keep replacing the number with the sum of the squares of its digits until we either reach 1 or the number starts repeating.
We define a helper function getNext that calculates the sum of the squares of the digits. We use an integer array to track seen numbers. If a number repeats, it means a cycle has formed and thus it is not a happy number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n), where n is the input number. Space Complexity: O(log n), as we store seen numbers.
This approach utilizes Floyd's Cycle-Finding Algorithm (also known as Tortoise and Hare). Instead of using a hash set, we can use two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time, whereas the fast pointer moves two steps at a time. If they meet, it means the sequence is cyclic.
We use two pointers (slow and fast). The slow pointer advances by one step, and the fast pointer by two. If they meet without reaching 1, it indicates a cycle.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n). Space Complexity: O(1), since no extra space is used apart from variables.
| Approach | Complexity |
|---|---|
| Approach 1: Using HashSet to Detect Cycles | Time Complexity: O(log n), where n is the input number. Space Complexity: O(log n), as we store seen numbers. |
| Approach 2: Floyd's Cycle-Finding Algorithm | Time Complexity: O(log n). Space Complexity: O(1), since no extra space is used apart from variables. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Cycle Detection | O(log n) | O(log n) | Best for clarity and straightforward cycle detection using a hash set |
| Floyd's Cycle-Finding (Fast & Slow Pointers) | O(log n) | O(1) | Preferred when memory usage matters or when demonstrating cycle detection optimization |
Happy Numbers | Number counting for kids • Happy Sunshine Friends • 225,752 views views
Watch 9 more video solutions →Practice Happy Number with our built-in code editor and test cases.
Practice on FleetCode