Domain 1EasyCORE

Happy Number

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).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Math

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 n where 1 <= n <= 2^31 - 1.

Outputs:

  • Return true if n is a happy number, otherwise return false.

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

  1. Initialize Two Pointers: Start with two variables, slow and fast, both set to the input number n.
  2. Cycle Detection Loop:
    • Calculate the next number for both slow and fast. For slow, move one step at a time by calculating the sum of squares of its digits. For fast, move two steps by applying the same calculation twice.
    • If slow equals fast, break out of the loop.
  3. Check for Happiness:
    • If slow is 1, then n is a happy number, so return true.
    • Otherwise, return false as it means we’ve detected a cycle.

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.