Happy Number - Solution & Explanation
Problem Statement
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.
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 - 1
Approach Overview
Problem Overview: 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 called a happy number. If the sequence enters a loop that never reaches 1, the number is not happy.
Approach 1: Using HashSet to Detect Cycles (O(log n) time, O(log n) space)
This approach simulates the process directly while tracking previously seen numbers. For each step, iterate through the digits of the current number, compute the sum of their squares, and generate the next value in the sequence. Store each intermediate value in a HashSet. If the sequence reaches 1, the number is happy. If a value repeats, the sequence has entered a cycle and will never reach 1.
The key insight is that unhappy numbers always fall into a repeating loop. A constant-time hash lookup detects when the loop starts. Each iteration processes the digits of the number, which takes O(log n) time because the number of digits grows logarithmically with n. The extra memory stores the sequence of previously seen values.
This method is straightforward and easy to reason about. If you're comfortable with hash tables, it's usually the fastest way to implement the solution during an interview.
Approach 2: Floyd's Cycle-Finding Algorithm (O(log n) time, O(1) space)
This approach eliminates the extra memory by treating the sequence as a linked list and detecting cycles using two pointers. Compute the next number using the same digit-square operation. Maintain a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If the number is happy, the sequence eventually reaches 1. If a cycle exists, the two pointers will meet at some point in the loop.
Floyd's algorithm works because any repeating sequence behaves like a cycle in a linked structure. The slow/fast pointer technique guarantees detection without storing previous values. Each step still requires computing digit squares, so the time complexity remains O(log n), but the space complexity drops to O(1).
This solution combines ideas from two pointers and math problems. It is slightly trickier to implement but demonstrates strong understanding of cycle detection patterns.
Recommended for interviews: Start with the HashSet approach to show clear reasoning about cycle detection. Once that works, mention Floyd's cycle-finding optimization to reduce space to O(1). Interviewers typically expect candidates to recognize the cycle and either detect it with a set or optimize it using two pointers.
Approach 1: Approach 1: Using HashSet to Detect Cycles
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.
Complexity
Time Complexity: O(log n), where n is the input number. Space Complexity: O(log n), as we store seen numbers.
Approach 2: Approach 2: Floyd's Cycle-Finding Algorithm
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.
Complexity
Time Complexity: O(log n). Space Complexity: O(1), since no extra space is used apart from variables.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Cycle Detection | O(log n) | O(log n) | Best for clarity and quick implementation. Easy way to detect repeating states. |
| Floyd's Cycle-Finding Algorithm | O(log n) | O(1) | Use when memory must be minimized or when demonstrating cycle detection skills. |
Video Solution
Happy Number - Leetcode 202 - Python • NeetCode • 125,002 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Happy Number easy or hard?
Happy Number Python/Java solution
How to solve Happy Number in O(1) space?
What is the best approach for Happy Number?
Is Happy Number asked at Google/Amazon/Meta?
What data structure is used in Happy Number?
What is the time complexity of Happy Number?
Ready to solve this problem?
Practice Happy Number with our built-in code editor and test cases.
Practice on FleetCode