Happy Number
Problem
Given an integer n, return true if it is a happy number, and false otherwise. A happy number is defined by repeatedly replacing the number by the sum of the squares of its digits until it equals 1 or it loops endlessly in a cycle that does not include 1.
- 1 ≤ n ≤ 2³¹ - 1
Example
n = 19trueStarting with 19, the algorithm computes the sum of squares of digits: 1² + 9² = 1 + 81 = 82. Then for 82: 8² + 2² = 64 + 4 = 68. For 68: 6² + 8² = 36 + 64 = 100. For 100: 1² + 0² + 0² = 1. Since the sequence reaches 1, 19 is a happy number and the function returns true.
Approach
Straightforward Solution
A naive approach would repeatedly compute the sum of squares and check if the number is 1, but without cycle detection, this can lead to infinite loops for unhappy numbers.
Core Observation
The process of repeatedly replacing a number by the sum of the squares of its digits either eventually reaches 1 (happy number) or falls into a cycle that never reaches 1. Detecting this cycle is essential to avoid infinite loops.
Path to Optimal
The key recognition signals are 'detect cycle' and 'avoid infinite loops'. These indicate using a Hash Map or Set to track previously seen numbers. By storing each intermediate number, the algorithm can detect when a cycle occurs (a repeated number) and terminate early. This transforms the problem from potentially infinite iteration to a guaranteed termination with O(k) complexity, where k is the number of unique intermediate numbers.
Optimal Approach
Use a set to record all numbers encountered during the transformation. In each iteration, compute the sum of squares of digits. If the result is 1, return true. If the number has been seen before, a cycle exists, so return false. This approach guarantees termination and correctness.
Time
O(log n)
Each iteration reduces the number roughly to the sum of squares of its digits, which is bounded by a function of the number of digits. Since the number of digits is O(log n), and each number is unique until a cycle or 1 is found, the total iterations are bounded by a small constant related to digit sums.
Space
O(log n)
The visited set stores each unique intermediate number encountered. Since numbers are bounded by digit sums, the set size is proportional to the number of unique states, which is O(log n) in the number of digits.
Pattern Spotlight
Hash Maps (Cycle Detection via Visited Set)
When a process involves repeated transformations that may cycle, use a hash set to record visited states and detect cycles early, preventing infinite loops and ensuring termination.
Solution
| 1 | class Solution:
|
| 2 | def isHappy(self, n: int) -> bool:
|
| 3 | visit = set()
|
| 4 |
|
| 5 | while n not in visit:
|
| 6 | visit.add(n)
|
| 7 | n = self.sumOfSquares(n)
|
| 8 |
|
| 9 | if n == 1:
|
| 10 | return True
|
| 11 |
|
| 12 | return False
|
| 13 |
|
| 14 | def sumOfSquares(self, n: int) -> int:
|
| 15 | output = 0
|
| 16 | while n:
|
| 17 | digit = n % 10
|
| 18 | digit = digit ** 2
|
| 19 | output += digit
|
| 20 | n = n // 10
|
| 21 | return output |
Step-by-Step Solution
Track Visited Numbers to Detect Cycles During Transformation
| 3 | visit = set()
|
Objective
To maintain a set of all numbers encountered to detect cycles and prevent infinite loops.
Key Insight
By storing each intermediate number in a set, the algorithm can quickly determine if the current number has appeared before, signaling a cycle. This prevents infinite repetition and ensures the algorithm terminates either by finding 1 or detecting a cycle.
Interview Quick-Check
Core Logic
Using a set to track visited numbers enables O(1) average-time cycle detection, which is essential for correctness and termination.
Common Pitfalls & Bugs
Failing to track visited numbers leads to infinite loops for unhappy numbers.
Iteratively Compute Sum of Squares and Check for Happiness or Cycle
| 5 | while n not in visit:
|
| 6 | visit.add(n)
|
| 7 | n = self.sumOfSquares(n)
|
| 9 | if n == 1:
|
| 10 | return True
|
| 12 | return False
|
Objective
To repeatedly transform the number by summing the squares of its digits and check for termination conditions.
Key Insight
The loop continues until the number is either 1 (happy) or repeats (cycle). Computing the sum of squares digit-by-digit ensures the transformation is correct. Checking for 1 immediately allows early termination for happy numbers.
Interview Quick-Check
Core Logic
The loop condition and checks ensure the algorithm terminates as soon as a happy number is found or a cycle is detected.
State & Boundaries
The loop continues while the current number has not been seen before, ensuring no repeated states.
Common Pitfalls & Bugs
Checking for 1 after updating the number is critical; missing this leads to incorrect results.
Calculate Sum of Squares of Digits for Current Number
| 14 | def sumOfSquares(self, n: int) -> int:
|
| 15 | output = 0
|
| 16 | while n:
|
| 17 | digit = n % 10
|
| 18 | digit = digit ** 2
|
| 19 | output += digit
|
| 20 | n = n // 10
|
| 21 | return output |
Objective
To compute the sum of the squares of each digit of the current number.
Key Insight
Breaking the number into digits using modulo and integer division allows precise calculation of the sum of squares. This transformation is the core operation that drives the state changes in the algorithm.
Interview Quick-Check
Core Logic
Digit extraction and squaring is done in a loop until the number is reduced to zero, ensuring all digits contribute to the sum.
Common Pitfalls & Bugs
Forgetting to update the number by integer division leads to infinite loops in digit processing.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
n = self.sumOfSquares(n)Update the current number to the sum of the squares of its digits.
This line implements the key state transition by replacing the current number with the sum of squares of its digits, which is the defining operation of the happy number sequence.
if n == 1:Check if the current number is 1, indicating a happy number.
This check is critical because reaching 1 is the success condition; returning true here ensures correct and efficient termination.
return FalseReturn false when a cycle is detected (number repeats without reaching 1).
Returning false here correctly identifies that the sequence has entered a cycle, proving the number is unhappy and preventing infinite loops.
visit = set()Initialize a set to store numbers already seen during the transformation process.
This set is essential for cycle detection, allowing the algorithm to identify repeated states and prevent infinite loops.
visit.add(n)Add the current number to the visited set.
Recording the current number marks it as seen, enabling future detection of cycles if the number reappears.
return outputReturn the computed sum of squares of digits.
Returning this value provides the next state in the happy number sequence transformation.
while n not in visit:Begin a loop that continues until the current number has been seen before.
This loop condition ensures the algorithm terminates either when a cycle is detected (number repeats) or when the number becomes 1 (happy number).
return TrueReturn true when the number is confirmed happy.
Returning immediately upon finding 1 prevents unnecessary further computation and signals success.
while n:Extract the last digit of the number using modulo 10.
Modulo operation isolates the least significant digit, enabling digit-wise processing.
digit = n % 10Square the extracted digit.
Squaring the digit is the core operation for the sum of squares transformation.
digit = digit ** 2Add the squared digit to the output accumulator.
Accumulating the squared digits builds the transformed number for the next iteration.
output += digitRemove the last digit from the number by integer division by 10.
Integer division truncates the processed digit, moving to the next digit in the next loop iteration.
output = 0Start a loop to process each digit of the number.
Iterating until the number is zero ensures all digits are processed exactly once.
n = n // 10Loop back to process the next digit until number is zero.
This loop ensures all digits are processed, completing the sum of squares calculation.
def sumOfSquares(self, n: int) -> int:Initialize the output sum for the sum of squares calculation.
This accumulator stores the sum of squared digits for the current number, resetting for each calculation.
Test Your Understanding
Why is it necessary to track previously seen numbers when determining if a number is happy?
Because without tracking, the process can enter an infinite cycle of numbers that never reach 1. Detecting repeated numbers indicates a cycle, allowing the algorithm to terminate and return false.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Happy Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Happy Number drill