The O(n) Club: Happy Number — When Integers Need Therapy

The O(n) Club: Happy Number — When Integers Need Therapy

⚡ TL;DR

Take a number. Replace it with the sum of the squares of its digits. Repeat. If you hit 1, congrats—your number is happier than you on Friday. If not, get ready for infinite déjà vu.
Basic (broken) brute force:

// Infinite-loop bait! Don't copy-paste this.
int n = 19; // Try n = 4 if masochism excites you
while (n != 1) {
    n = sumOfSquares(n); // Whoops, is this a black hole?
}
// You might age here.
  

🧠 How Devs Usually Mess This Up

Picture a hopeful junior dev saying, “Surely, if I keep squaring and summing, I’ll reach 1!” Fast-forward 5 years—your PC’s fan is louder than your existential thoughts. Why? Some numbers just love to cycle in eternal misery. If you don’t record where you’ve been, your code’s going red-hot, not your LinkedIn.

🔍 What’s Actually Going On

Imagine a robot chef making potato salad. Every minute, it picks random potatoes (digits), squares them, and throws it all back in the pot (the sum). If it ever remakes a batch exactly like before, it’s trapped in a kitchen loop—never reaching the fabled “single happy potato.” Use a HashSet like a logbook so the chef knows if it’s seen that batch before. Or, geek out and use Floyd’s Tortoise & Hare: send two robots (one slow, one fast) scooting along—when they collide, stop the madness.

🛠️ PseudoCode

• Initialize a HashSet for seen numbers:
  

  Set<Integer> seen = new HashSet<>();

  // Think of it as your robot’s memory chip.
• Loop until n == 1:
  

  while (n != 1) { ... }

  // Escaping the loop = happiness; stuck = therapy bills.
• If n is in seen, return false (loop detected):
  

  if (seen.contains(n)) return false;

  // Welcome back to where you started – classic infinite kitchen.
• Add n to seen, update n:
  

  seen.add(n); n = sumOfSquares(n);

  // The chef scribbles in the logbook, then mixes again.
• If n hits 1, it’s a Happy Number. Serve with a smile.

💻 The Code

public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1) {
        if (seen.contains(n)) return false;
        seen.add(n);
        n = sumOfSquares(n);
    }
    return true;
}
 private int sumOfSquares(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Forget to check for cycles? Congrats, you’ve built the universe’s smallest perpetual motion machine. Next time, use a Set.
• Negative inputs? Don’t bother. This code’s for positive integers only — like your cheeriest optimism, not for Mondays.
• Time/Space: Max digit-squares are tiny, and most unhappy sequences loop quick. Space is O(unique values seen), but that’s rarely big outside TikTok algorithms.

🧠 Interviewer Brain-Tattoo

If your happy number code forgets cycle detection, the only thing in an endless loop will be your job search.