Happy Number - Video Solutions

Problem Overview: Given an integer n, repeatedly replace the number with the sum of the squares of its digits. If the process eventually reaches 1, the number is called a happy number. If the sequence enters a loop that never reaches 1, the number is not happy.

Approach 1: Using HashSet to Detect Cycles (O(log n) time, O(log n) space)

This approach simulates the process directly while tracking previously seen numbers. For each step, iterate through the digits of the current number, compute the sum of their squares, and generate the next value in the sequence. Store each intermediate value in a HashSet. If the sequence reaches 1, the number is happy. If a value repeats, the sequence has entered a cycle and will never reach 1.

The key insight is that unhappy numbers always fall into a repeating loop. A constant-time hash lookup detects when the loop starts. Each iteration processes the digits of the number, which takes O(log n) time because the number of digits grows logarithmically with n. The extra memory stores the sequence of previously seen values.

This method is straightforward and easy to reason about. If you're comfortable with hash tables, it's usually the fastest way to implement the solution during an interview.

Approach 2: Floyd's Cycle-Finding Algorithm (O(log n) time, O(1) space)

This approach eliminates the extra memory by treating the sequence as a linked list and detecting cycles using two pointers. Compute the next number using the same digit-square operation. Maintain a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If the number is happy, the sequence eventually reaches 1. If a cycle exists, the two pointers will meet at some point in the loop.

Floyd's algorithm works because any repeating sequence behaves like a cycle in a linked structure. The slow/fast pointer technique guarantees detection without storing previous values. Each step still requires computing digit squares, so the time complexity remains O(log n), but the space complexity drops to O(1).

This solution combines ideas from two pointers and math problems. It is slightly trickier to implement but demonstrates strong understanding of cycle detection patterns.

Recommended for interviews: Start with the HashSet approach to show clear reasoning about cycle detection. Once that works, mention Floyd's cycle-finding optimization to reduce space to O(1). Interviewers typically expect candidates to recognize the cycle and either detect it with a set or optimize it using two pointers.