202. Happy Number
Model: qwen2.5-coder:14b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 51.4%
Problem Breakdown
The problem asks us to determine if a given number n is a happy number. A happy number is defined by repeatedly replacing the number with the sum of the squares of its digits until either the number becomes 1 (indicating it’s a happy number) or it falls into an endless cycle that does not include 1 (indicating it’s not a happy number).
Inputs:
- A positive integer
nwhere1 <= n <= 2^31 - 1.
Outputs:
- Return
trueifnis a happy number, otherwise returnfalse.
Implicit Constraints or Tricky Edge Cases:
- The process could potentially run indefinitely if the number does not become 1.
- We need to detect cycles efficiently to avoid infinite loops.
Intuition
A brute-force approach would involve repeatedly calculating the sum of squares of digits until we either reach 1 or manually track a large number of iterations. However, this is inefficient and may lead to excessive time complexity without cycle detection.
The key insight is that if a number is not happy, it will eventually fall into a cycle. We can use Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm) to detect cycles efficiently. This approach involves using two pointers: one moving twice as fast as the other. If there is a cycle, the fast pointer will eventually meet the slow pointer.
Approach
- Initialize Two Pointers: Start with two variables,
slowandfast, both set to the input numbern. - Cycle Detection Loop:
- Calculate the next number for both
slowandfast. Forslow, move one step at a time by calculating the sum of squares of its digits. Forfast, move two steps by applying the same calculation twice. - If
slowequalsfast, break out of the loop.
- Calculate the next number for both
- Check for Happiness:
- If
slowis 1, thennis a happy number, so returntrue. - Otherwise, return
falseas it means we’ve detected a cycle.
- If
Complexity Analysis
- Time Complexity: O(log n) in the best case (when the number becomes 1 quickly), and potentially O(k log n) in the worst case where k is the length of the cycle. The sum of squares operation takes O(log n) time.
- Space Complexity: O(1) since we are using a constant amount of extra space.
Solution
def isHappy(n: int) -> bool:
def get_next(number):
total_sum = 0
while number > 0:
digit = number % 10
total_sum += digit * digit
number //= 10
return total_sum
slow = n
fast = get_next(n)
while slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return slow == 1
Edge Cases Handled
- Single Digit Numbers: The algorithm correctly handles single-digit numbers, as they will either be happy (e.g., 1) or not (e.g., 2).
- Cycle Detection: The use of Floyd’s Cycle-Finding Algorithm ensures that we can detect cycles efficiently without excessive memory usage.
- Large Input Range: Given the constraints
1 <= n <= 2^31 - 1, the algorithm handles large numbers by focusing on digit operations, which are efficient.