How do you solve Happy Number on LeetCode?

Happy Number (LeetCode #202) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Happy numbers eventually reach 1 or fall into a cycle.

What is the brute force solution for Happy Number?

The brute force approach for Happy Number is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach repeatedly calculates the sum of the squares of the digits of the number until we either reach 1 or detect a cycle. This is straightforward but can be inefficient due to potential repeated calculations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Happy Number?

Happy Number uses the following concepts: Hash Table, Math, Two Pointers. The recommended patterns to study are: Hash Map, Two Pointers.

What are the interview tips for Happy Number?

Explain your thought process clearly; mention cycle detection early. Consider edge cases, like the smallest happy number (1). Discuss time and space complexity as you go.

What are common mistakes when solving Happy Number?

Not checking for cycles, leading to infinite loops. Confusing the sum of squares with just squaring the number.

#202

Happy Number

Easy

Hash TableMathTwo PointersHash MapTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses the Floyd's Cycle detection algorithm (Tortoise and Hare) to detect cycles without extra space. This is efficient because it avoids storing all seen numbers and only uses two pointers.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, slow and fast. Both start at n.
2Step 2: Move slow pointer one step (sum of squares of digits) and fast pointer two steps (sum of squares of digits twice).
3Step 3: If slow equals fast and it's not 1, a cycle exists, return false.
4Step 4: If slow equals 1, return true (happy number).
5Step 5: Repeat until a conclusion is reached.

solution.py9 lines

1def isHappy(n):
2    def get_next(num):
3        return sum(int(x) ** 2 for x in str(num))
4    slow = n
5    fast = get_next(n)
6    while fast != 1 and slow != fast:
7        slow = get_next(slow)
8        fast = get_next(get_next(fast))
9    return fast == 1

ℹ

Complexity note: The time complexity is O(n) because we may need to compute the sum of squares for each number until we reach 1 or detect a cycle, and we only use constant space for the two pointers.

1Happy numbers eventually reach 1 or fall into a cycle.
2Using a set can help detect cycles, but Floyd's algorithm is more space-efficient.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.