Happy Number Algorithm Solution

The happy number problem requires determining if a number eventually reaches 1 when replaced by the sum of squares of its digits. This solution presents an efficient approach using hash sets to detect cycles in the sequence.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input be negative, or is it guaranteed to be a positive integer?
2. What should we return if the number is happy or not happy? (boolean, true/false, or just print result?)
3. Are we allowed to mutate the input number during computation?
4. What's the expected time complexity for the solution? (e.g., O(log n) or better?)
5. How large can the input number be? (e.g., up to Integer.MAX_VALUE?)

Restatement in my own words: A happy number is a positive integer where repeatedly replacing the number with the sum of squares of its digits eventually leads to 1. If it loops endlessly in a cycle without reaching 1, then the number is not happy.

Clarification of inputs, outputs, and constraints:

• Input: A positive integer n
• Output: Boolean indicating whether the number is happy (true if happy, false otherwise)
• Constraints:
  • The input is a positive integer (no negative numbers or zero)
  • We can assume the input will not cause overflow in intermediate calculations
  • The process of computing sum of squares can be repeated until either we reach 1 or detect a cycle

Assumptions I'm making:

• The input will always be a positive integer (as per definition of happy numbers)
• We can use additional space to track previously seen numbers for cycle detection
• The solution should return a boolean value indicating happy/not happy status

Data shape and hidden structure: The problem involves iterative mathematical operations on digits of a number. Each iteration transforms the current number into the sum of squares of its digits, creating a sequence that either converges to 1 or enters a cycle. The hidden structure is that if we keep track of all numbers we've seen, we can detect cycles using a HashSet. This suggests that the problem has a graph traversal or cycle detection pattern, where each number points to another number in the sequence.

The key insight is that once we've seen a number before in our computation path, we know we're in a loop and the number is not happy.

2. Pattern Recognition

The problem asks us to determine if a number is "happy" - a number where repeatedly replacing it with the sum of squares of its digits eventually leads to 1. If it enters a cycle that doesn't include 1, it's not happy.

Most likely pattern: Cycle detection in a sequence of numbers

Wording that signals the pattern:

• "repeatedly replacing it with the sum of squares of its digits" - This creates a sequence where each element depends on the previous one
• "eventually leads to 1" - This suggests we're looking for a specific terminal state
• "if it loops endlessly in a cycle" - This explicitly mentions cycles, which is the key insight

Why this fits that pattern: This problem creates a deterministic sequence where each number maps to exactly one next number. Since we're dealing with digits, the sequence is bounded (each digit contributes at most 81 to the sum). Eventually, either:

1. We reach 1 (happy number)
2. We enter a cycle that never includes 1 (not happy)

Core insight: The key insight is that we can detect cycles in this sequence using either a HashSet to track seen numbers or Floyd's cycle detection (tortoise and hare). Since the sequence is deterministic and bounded, cycles will eventually occur if we don't reach 1.

The mathematical structure here is that we're traversing a directed graph where each node (number) has exactly one outgoing edge (the sum of squares of digits), and we're looking for either termination at 1 or a cycle in the graph traversal.

3. Approach Evolution

My first instinct is to simulate the process described in the problem - repeatedly calculate the sum of squares of digits until we either reach 1 (happy) or detect a cycle (not happy). But that's O(n²) in the worst case because we might have to compute many intermediate sums and check for cycles inefficiently.

Let me think about how to optimize this. I notice that if I maintain a set of previously seen numbers, I can detect cycles in O(1) time using a HashSet. This reduces the cycle detection from O(n²) to O(n) overall.

The key insight is that if we keep track of all numbers we've seen during our computation path, we can detect cycles immediately when we encounter a number we've seen before. This is the fundamental optimization - instead of potentially computing thousands of steps, we can detect a loop in O(n) time.

I'll use the Floyd's Cycle Detection algorithm (tortoise and hare) as an alternative approach, but for now I'll stick with the HashSet approach since it's more straightforward to understand and implement correctly.

The main invariant I need to maintain is that at each step, I'm either:

1. Computing the sum of squares correctly
2. Detecting that we've seen this number before (cycle detected)
3. Having reached 1 (happy number found)

This approach ensures we never process the same number twice, and we terminate when either we find 1 or detect a cycle.

The optimization is simple but powerful: use a HashSet to store all previously seen numbers, allowing O(1) lookup time to detect cycles. This transforms the problem from potentially infinite loop to bounded O(n) time complexity where n is the number of unique intermediate values before cycle detection.

4. Data Structure Choice

For this problem, I need to track which numbers I've seen during the process to detect cycles. The most appropriate data structure is a HashSet to store previously encountered numbers.

Primary Data Structure: HashSet

• Used to efficiently detect cycles in the sequence of numbers
• Provides O(1) average time complexity for both insertion and lookup operations
• Allows me to quickly determine if a number has been seen before

Why HashSet is ideal:

• The problem requires detecting when we enter a cycle (repeating number)
• HashSet's constant-time lookup makes it perfect for this detection
• It naturally handles the "seen before" check without requiring sorting or additional tracking

Time and Space Impact:

• Time complexity for cycle detection: O(1) average case
• Space complexity: O(k) where k is the number of unique numbers in the sequence before cycle detection
• This is optimal for cycle detection problems since we must store at least some representation of visited numbers

Helper Structure:

• No additional helper structures needed beyond the HashSet for cycle detection
• The algorithm can be implemented with just the input number and the HashSet

This choice directly supports the core insight that we need to detect cycles efficiently, which is fundamental to solving whether a number is happy.

5. Algorithm Walkthrough

Let me trace through the algorithm with the example of n = 19:

Step 1: Start with n = 19

• Calculate sum of squares: 1² + 9² = 1 + 81 = 82
• Add 82 to the HashSet: {82}
• Continue loop

Step 2: n = 82

• Calculate sum of squares: 8² + 2² = 64 + 4 = 68
• Add 68 to the HashSet: {82, 68}
• Continue loop

Step 3: n = 68

• Calculate sum of squares: 6² + 8² = 36 + 64 = 100
• Add 100 to the HashSet: {82, 68, 100}
• Continue loop

Step 4: n = 100

• Calculate sum of squares: 1² + 0² + 0² = 1 + 0 + 0 = 1
• Add 1 to the HashSet: {82, 68, 100, 1}
• Continue loop

Step 5: n = 1

• Calculate sum of squares: 1² = 1
• Check HashSet: 1 is already present → Found cycle!
• Return true (happy number)

The algorithm correctly identifies that 19 is a happy number because it eventually reaches 1 and doesn't enter a cycle with any previous sum.

For n = 2 (which is not happy):

• The sequence would be: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
• At this point, we encounter 4 again, which was seen before
• HashSet contains {2, 4, 16, 37, 58, 89, 145, 42, 20}
• When we reach 4 again, we detect the cycle and return false

The key insight is that if a number is not happy, it will eventually produce a sum that was seen before, creating a cycle in our HashSet tracking.

The algorithm terminates correctly because either:

1. We reach 1 (happy number case) - return true
2. We detect a cycle in our HashSet (unhappy number case) - return false

Both termination conditions are well-defined and handle all edge cases properly.

6. Java Solution

public class Solution {
    public boolean isHappy(int n) {
        // Use a HashSet to detect cycles
        java.util.Set<Integer> seen = new java.util.HashSet<>();
        
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getSumOfSquares(n);
        }
        
        // If we exit the loop because n == 1, it's a happy number
        return n == 1;
    }
    
    private int getSumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

The solution uses a HashSet to track numbers we've already seen to detect cycles. When we encounter a number we've seen before, we know we're in a loop and can return false. Otherwise, if we reach 1, the number is happy.

The helper method getSumOfSquares extracts each digit using modulo and division operations, squares each digit, and accumulates the sum. This is a clean way to process individual digits from right to left.

The main loop continues until either we reach 1 (happy number) or detect a cycle (not happy). The HashSet ensures O(1) lookup time for cycle detection.

7. Complexity Analysis

Time Complexity: O(log n) on average, O(log²n) worst case

The algorithm's time complexity depends on the cycle detection behavior. In the best case, a happy number will reach 1 quickly, requiring O(log n) operations where log n represents the number of digits in the input. In the worst case, when we enter a cycle that doesn't include 1, we might need to process up to O(log²n) numbers before detecting the cycle.

Each number processing involves:

• Calculating sum of squares of digits: O(log n) time
• Checking membership in HashSet: O(1) average case, O(log n) worst case for hash collision handling

Space Complexity: O(log n)

The space complexity is dominated by the HashSet storing previously seen numbers. In the worst case, we might store all numbers in a cycle before detecting repetition, which can be at most O(log n) numbers since the maximum number of unique intermediate values is bounded by the range of possible sums.

Why these bounds are correct:

The bounds hold because:

1. Each number in the sequence has at most O(log n) digits, so processing each number takes O(log n) time
2. The HashSet operations are amortized O(1) but can degrade to O(log n) in worst-case hash collisions
3. The maximum number of unique values in the sequence is bounded by the mathematical properties of the digit sum process, which limits the growth to O(log n) in the number of distinct intermediate values

Optimality:

This solution is near-optimal for the given constraints. Since we must examine each number in the sequence to detect cycles, and we must store previously seen numbers to avoid infinite loops, O(log n) time complexity is the best achievable for this problem in the general case. The solution avoids recomputation and uses efficient data structures to minimize constant factors.

The algorithm is optimal because:

• We cannot skip any intermediate numbers in the sequence without risking missing cycles
• The HashSet provides the most efficient way to detect duplicates among intermediate values
• Any improvement would require mathematical insights that could reduce the number of operations, but none exist for this general case

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• The problem defines happy numbers for positive integers only, so there's no valid "empty" input
• The smallest valid input is 1 (which is happy) and 2 (which is not happy)
• Edge case: input = 1 should return true immediately

Duplicate Values and Infinite Loops

• The key pitfall is detecting cycles in the sequence generation
• Without proper cycle detection, the algorithm will run infinitely for unhappy numbers
• The HashSet-based approach is essential to catch repeated sums and terminate correctly

Boundary Conditions

• Single digit numbers (1-9): Only 1 and 7 are happy numbers
• Large numbers: The sum of squares can quickly exceed Integer.MAX_VALUE, but this is handled by the mathematical property that we'll eventually cycle
• The algorithm must handle numbers up to 2^31 - 1 efficiently

Common Implementation Mistakes

• Incorrect cycle detection: Using a simple loop counter instead of tracking actual sums seen
• Integer overflow: Not considering that sum of squares can exceed int range, though mathematical properties prevent infinite loops
• Off-by-one errors: Miscounting iterations or not properly handling the final condition check
• Missing return statement: Failing to return false when a cycle is detected

Key Implementation Notes

• The algorithm should detect cycles by storing previously seen sums, not just counting iterations
• When a sum repeats, we know we're in a loop and can immediately return false
• The mathematical property that all unhappy numbers eventually cycle through the same set of sums makes this approach reliable
• Testing with known happy numbers (1, 7, 10, 13, 19, 23, 28, 31) helps validate cycle detection logic

9. Alternative Approaches

There are several alternative approaches to solving the Happy Number problem, each with different trade-offs:

1. Using a HashSet for cycle detection (Alternative to Floyd's Cycle Detection): Instead of using two pointers, we could use a HashSet to track all previously seen numbers. When we encounter a number we've seen before, we have a cycle and the number is not happy. This approach has O(log n) space complexity but is more intuitive to understand.

2. Mathematical Analysis Approach: We could analyze the mathematical properties of happy numbers more deeply. Since the sum of squares of digits eventually leads to cycles, we could precompute and store all happy numbers up to a certain limit. This would be O(1) for lookup but requires prior knowledge of the mathematical properties and doesn't scale well.

3. Recursive Approach with Memoization: We could implement a recursive solution that checks if each number in the sequence is happy, memoizing results to avoid recomputation. This would have O(log n) space for the recursion stack and memoization table, but is less efficient than the iterative approaches.

Trade-offs: The original Floyd's Cycle Detection approach is preferred because it uses O(1) space complexity, making it more memory-efficient than the HashSet approach. It's also more elegant and follows the mathematical structure of the problem better than mathematical analysis or recursion approaches. The two-pointer technique is particularly clean and avoids the overhead of maintaining additional data structures.

The HashSet approach is more readable but uses extra space, while the mathematical analysis approach requires deeper mathematical insight and doesn't scale well for arbitrary inputs.

10. Test Cases

public class HappyNumberTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic happy number
        // 19 -> 1² + 9² = 82 -> 64 + 4 = 68 -> 36 + 64 = 100 -> 1 + 0 + 0 = 1
        System.out.println("Test 1 - Happy number: " + isHappy(19)); // Expected: true
        
        // Test case 2: Basic unhappy number  
        // 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 (cycle)
        System.out.println("Test 2 - Unhappy number: " + isHappy(2)); // Expected: false
        
        // Test case 3: Single digit happy number
        System.out.println("Test 3 - Single digit happy: " + isHappy(1)); // Expected: true
        
        // Test case 4: Single digit unhappy number
        System.out.println("Test 4 - Single digit unhappy: " + isHappy(2)); // Expected: false
        
        // Test case 5: Edge case - zero
        System.out.println("Test 5 - Zero: " + isHappy(0)); // Expected: false
        
        // Test case 6: Larger happy number
        System.out.println("Test 6 - Large happy: " + isHappy(7)); // Expected: true
        
        // Test case 7: Another unhappy number with longer cycle
        System.out.println("Test 7 - Unhappy long cycle: " + isHappy(4)); // Expected: false
    }
    
    public static boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getSumOfSquares(n);
        }
        
        return n == 1;
    }
    
    private static int getSumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

Sample test cases include:

• Happy number 19: Follows the sequence 19 → 82 → 68 → 100 → 1 (happy)
• Unhappy number 2: Enters cycle 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (unhappy)
• Edge case 1: Single digit happy number (1)
• Edge case 2: Single digit unhappy number (2)
• Edge case 3: Zero input
• Large happy number: Testing with 7 (happy)
• Long cycle unhappy: Testing with 4 which has a longer cycle before repeating

The test cases cover the core behavior of happy numbers, including cycles that lead to termination and various edge conditions.

11. Final Summary

The core idea is to detect cycles in a sequence generated by repeatedly summing the squares of digits using a HashSet for cycle detection. This solution works because either the process terminates at 1 (happy number) or enters a cycle that will be detected by the HashSet. The approach is optimal with O(log n) time complexity for each iteration and O(log n) space complexity, making it efficient for the given constraints where numbers can be up to 2^31 - 1. The solution elegantly handles all edge cases including single digits, large numbers, and the mathematical properties that define happy numbers.