Happy Number Algorithm

Problem Description

Determine if a number n is a happy number. A happy number is defined by repeatedly replacing the number by the sum of the squares of its digits until it equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Return true if n is a happy number, and false if not.

Brute Force Solution

A brute force solution involves simulating the process as described, but we need a way to detect cycles to avoid infinite loops. We can use a HashSet to keep track of the numbers we've seen so far. If we encounter a number that's already in the set, we know we're in a cycle and the number is not happy.

Algorithm

1. Create a HashSet to store the numbers seen.
2. While the number n is not 1 and is not in the HashSet:
   • Add n to the HashSet.
   • Compute the sum of the squares of the digits of n and update n with the result.
3. If n is 1, return true. Otherwise, return false.

Code (Java)

import java.util.HashSet;
import java.util.Set;

public class HappyNumber {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            int sum = 0;
            int num = n;
            while (num > 0) {
                int digit = num % 10;
                sum += digit * digit;
                num /= 10;
            }
            n = sum;
        }
        return n == 1;
    }
}

Big O Analysis

• Time Complexity: O(log n) in the average case. In the worst case where the number loops endlessly, it can be considered O(1) as the range of numbers is constrained by the integer limits.
• Space Complexity: O(log n) in the average case to store the seen numbers in the HashSet. In the worst case it is O(1).

Optimal Solution

An optimized solution uses Floyd's Cycle Detection Algorithm, also known as the "tortoise and hare" algorithm. We use two pointers, one moving one step at a time (tortoise) and another moving two steps at a time (hare). If n is a happy number, the hare will eventually reach 1. If n is not a happy number, the two pointers will eventually meet at a number other than 1.

Algorithm

1. Initialize two pointers, slow and fast, to n.
2. While fast is not 1 and slow is not equal to fast:
   • Move slow one step: slow = sumOfSquares(slow)
   • Move fast two steps: fast = sumOfSquares(sumOfSquares(fast))
3. If fast is 1, return true. Otherwise, return false.

Code (Java)

public class HappyNumber {
    private int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do {
            slow = sumOfSquares(slow);
            fast = sumOfSquares(sumOfSquares(fast));
        } while (slow != fast);
        return slow == 1;
    }
}

Big O Analysis

• Time Complexity: O(log n) in the average case. This is because the number of steps to reach 1 or a cycle is logarithmic to the input number. In the worst case, it's still considered O(1) as the range of numbers is bounded.
• Space Complexity: O(1). We use only two integer variables, slow and fast, regardless of the input size.

Edge Cases

• n = 1: Should return true immediately.
• Large n: The algorithm should work for any positive integer within the specified constraints.
• Cyclic numbers: The algorithm must correctly detect cycles to avoid infinite loops, achieved effectively by both the HashSet approach and the Floyd's cycle detection approach.