Happy Number
Asked at Google, Amazon, Apple, Microsoft
Problem
Happy Number asks you to determine whether a number is "happy" — meaning that repeatedly replacing it with the sum of the squares of its digits eventually reaches 1. Numbers that do not reach 1 enter a cycle. This problem combines math with cycle detection.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Apple | Easy | View all Apple questions → |
| Microsoft | Easy | View all Microsoft questions → |
How to Think About It
Simulate the process: repeatedly compute the sum of squares of digits. Use a hash set to track numbers you have seen. If you see a number again, you are in a cycle and it is not happy. If you reach 1, it is happy.
Optimal: use Floyd's cycle detection (tortoise and hare). Instead of a hash set, use two pointers — one moves one step at a time, the other moves two steps. If they meet, there is a cycle. If the slow pointer reaches 1, it is happy. O(1) space.
Why cycles always exist: there are only finitely many possible values for a given number of digits. For a 32-bit integer, the sum of squares of digits is at most 9²×10 = 810. So after the first iteration, values are bounded. With finite states, you must eventually repeat.
The sum of squares of digits function: for n = 19: 1² + 9² = 1 + 81 = 82. For n = 82: 8² + 2² = 64 + 4 = 68. Keep going until you reach 1 or see a repeat.
Edge cases: n = 1 is happy by definition. n = 0 is not happy (0² = 0, stuck at 0). Negative numbers — the problem says positive integers, so no need to handle negatives.
Optimal Approach
Use Floyd's cycle detection. Initialize slow = n, fast = n. In each iteration, slow moves one step (sum of squares of digits once), fast moves two steps (sum of squares of digits twice). If slow == fast, check if slow == 1 — if yes, return true (happy); if no, return false (cycle).
Walkthrough: n = 19. slow: 19→82→68→100→1→1. fast: 19→68→1→1. They meet at 1. Result: true.
Time: O(log n) per iteration, O(log n) iterations. Space: O(1) — only two pointers.
What Trips People Up in Real Interviews
Not recognizing this as a cycle detection problem. The interviewer is testing whether you see the analogy to linked list cycles.
Using a hash set when Floyd's algorithm is expected. Both work, but Floyd's shows deeper understanding of cycle detection and uses O(1) space.
Getting the digit extraction wrong. Be careful with integer division: for 19, 19 % 10 = 9, 19 // 10 = 1, 1 % 10 = 1, 1 // 10 = 0.
Forgetting that the problem guarantees a positive integer. Don't waste time on negative number edge cases.
Solution Code
def isHappy(n):
def get_next(num):
total = 0
while num > 0:
num, digit = divmod(num, 10)
total += digit * digit
return total
slow = n
fast = get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1Frequently Asked Questions
What is the Happy Number problem?
Happy Number asks you to determine whether a number is "happy" — meaning that repeatedly replacing it with the sum of the squares of its digits eventually reaches 1. Numbers that do not reach 1 enter a cycle. This problem combines math with cycle detection.
How do you solve Happy Number?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Happy Number?
Happy Number is asked at Google, Amazon, Apple, Microsoft. It is a easy difficulty problem.
What are common mistakes on Happy Number?
- Not recognizing this as a cycle detection problem. The interviewer is testing whether you see the analogy to linked list cycles.
- Using a hash set when Floyd's algorithm is expected. Both work, but Floyd's shows deeper understanding of cycle detection and uses `O(1)` space.
- Getting the digit extraction wrong. Be careful with integer division: for 19, 19 % 10 = 9, 19 // 10 = 1, 1 % 10 = 1, 1 // 10 = 0.
- Forgetting that the problem guarantees a positive integer. Don't waste time on negative number edge cases.