Happy Number

How it works

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1.

Just like before, this process either:

• reaches 1 → happy number
• falls into a cycle → not a happy number

This solution uses a different cycle detection method called Brent's Algorithm, which is another form of fast–slow pointer technique.

Key idea:

• We still move through the sequence n → sumOfSquares(n)
• But instead of moving one pointer twice as fast every step, we:
  • increase the distance between comparisons in powers of two
• This reduces the number of comparisons and still guarantees cycle detection

We keep track of:

• slow → a checkpoint value
• fast → the moving value
• power → how far we go before resetting slow
• lam → current distance since last reset

If fast ever equals slow, a cycle is detected.

Steps

1. Initialize:
   • slow = n
   • fast = sumOfSquares(n)
   • power = 1 (current block size)
   • lam = 1 (steps taken in current block)
2. While slow != fast:
3. If power == lam:
   • move the checkpoint:
     • slow = fast
   • double the block size:
     • power *= 2
   • reset step counter:
     • lam = 0
4. Move fast one step forward:
   • fast = sumOfSquares(fast)
5. Increment lam by 1.
6. When the loop ends, a cycle is detected.
7. If fast == 1:
   • the cycle ends at 1
   • return true
8. Otherwise:
   • return false

---

Helper Function (Sum of Squares)

To compute the next number:

1. Initialize output = 0
2. While n > 0:
   • extract the last digit using n % 10
   • square it and add to output
   • remove the digit using n //= 10
3. Return output

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Infinite Loop Without Cycle Detection

Forgetting to detect cycles causes the program to loop forever for non-happy numbers. Without a hash set or fast/slow pointers, numbers like 2 will endlessly cycle through the same values (2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...) without ever reaching 1.

Incorrect Digit Extraction

Using the wrong operations to extract digits leads to incorrect sum calculations. A common mistake is forgetting integer division when removing the last digit (n = n // 10) or using string conversion inefficiently. Always use n % 10 to get the last digit and n // 10 to remove it.

class Solution:
    def isHappy(self, n: int) -> bool:
        slow, fast = n, self.sumOfSquares(n)
        power = lam = 1

        while slow != fast:
            if power == lam:
                slow = fast
                power *= 2
                lam = 0
            fast = self.sumOfSquares(fast)
            lam += 1
        return True if fast == 1 else False

    def sumOfSquares(self, n: int) -> int:
        output = 0

        while n:
            digit = n % 10
            digit = digit ** 2
            output += digit
            n = n // 10
        return output

class Solution {
public:
    bool isHappy(int n) {
        int slow = n, fast = sumOfSquares(n);
        int power = 1, lam = 1;

        while (slow != fast) {
            if (power == lam) {
                slow = fast;
                power *= 2;
                lam = 0;
            }
            lam++;
            fast = sumOfSquares(fast);
        }

        return fast == 1;
    }

private:
    int sumOfSquares(int n) {
        int output = 0;
        while (n != 0) {
            output += (n % 10) * (n % 10);
            n /= 10;
        }
        return output;
    }
};