Happy Number - Video Solutions

Problem Overview: You are 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 considered a happy number. If it falls into a repeating cycle that never reaches 1, it is not.

Approach 1: Using HashSet to Detect Cycles (Time: O(log n), Space: O(log n))

This approach simulates the process directly and tracks previously seen numbers using a hash set. For each iteration, compute the sum of the squares of the digits of the current number. If the result becomes 1, the number is happy. If you encounter a value that already exists in the set, a cycle has formed and the sequence will never reach 1. The key insight is that unhappy numbers always enter a loop (for example, 4 → 16 → 37 → ... → 4). Hash lookups allow constant-time cycle detection, making the simulation efficient. This approach relies on a hash table to remember visited states and works well for explaining the logic during interviews.

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

Instead of storing visited values, you can detect the cycle using the classic fast and slow pointer technique. Treat each transformation as a step in a sequence: next(n) computes the sum of squares of digits. Maintain two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps (next(next(n))). If the number is happy, both pointers eventually reach 1. If the sequence contains a cycle, the two pointers will meet at some value inside the loop. This technique is widely used in linked list cycle detection and fits well here because the transformation defines a deterministic sequence. It avoids extra memory and demonstrates knowledge of the two pointers pattern combined with basic math operations.

Recommended for interviews: Start with the HashSet approach because it clearly demonstrates the idea of detecting repeated states in a sequence. Once the cycle concept is clear, optimize the solution using Floyd's cycle detection to reduce space to O(1). Interviewers typically expect the cycle insight; showing both approaches signals strong problem-solving depth.