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 - 1The key idea behind Happy Number is repeatedly replacing a number with the sum of the squares of its digits. If the process eventually reaches 1, the number is considered happy. However, some numbers fall into a repeating cycle that never reaches 1. Detecting this cycle is the main challenge.
A common approach uses a hash set to store previously seen numbers. During each iteration, compute the digit-square sum and check if it has appeared before. If it repeats, a cycle exists and the number is not happy. If the sequence reaches 1, the number is happy.
An alternative technique uses the two pointers (Floyd’s cycle detection) method. One pointer moves one step at a time while the other moves two steps. If they meet before reaching 1, a cycle exists.
Both approaches efficiently detect loops, keeping the process bounded with near constant time behavior.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set (Cycle Detection) | O(log n) | O(log n) |
| Floyd’s Two Pointers | O(log n) | O(1) |
Happy Sunshine Friends
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.
Time Complexity: O(log n), where n is the input number. Space Complexity: O(log n), as we store seen numbers.
1#include <unordered_set>
2
3bool isHappy(int n) {
4 auto getNext = [](int n) {
5 int totalSum = 0;
6 while (n > 0) {
7 int d = n % 10;
8 n /= 10;
9 totalSum += d * d;
10 }
11 return totalSum;
12 };
13 std::unordered_set<int> seen;
14 while (n != 1 && seen.find(n) == seen.end()) {
seen.insert(n);
n = getNext(n);
}
return n == 1;
}The unordered_set is used to keep track of all previously seen numbers. If we encounter a number that we have seen before, it means we are in a cycle. We repeatedly replace the number with the sum of the squares of its digits until we reach 1 or a cycle is detected.
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.
Time Complexity: O(log n). Space Complexity: O(1), since no extra space is used apart from variables.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Happy Number is a common easy-level interview problem. It tests understanding of cycle detection, hash sets, and mathematical digit manipulation.
A common optimal approach is using Floyd’s cycle detection algorithm (two pointers). It detects repeating cycles without storing visited values, giving O(1) space complexity while maintaining efficient runtime.
When repeatedly squaring and summing digits, the values eventually shrink into a small range. Numbers that do not reach 1 eventually repeat a previous value, forming a cycle.
A hash set is often used to store previously generated numbers in the sequence. If a number repeats, it means the process has entered a cycle and the number is not happy.
Java implementation of Floyd's cycle detection. The slow pointer goes step by step, while the fast pointer advances quickly. Meeting indicates a loop unless one hits 1.