Happy Number

Happy Number looks like a small math puzzle. But it hides a real test. The interviewer wants to see if you can spot a loop that never ends. Then they want to see how you stop it. That is the actual skill being checked here.

🎯 The Problem

You get a positive number and repeat one simple step on it.

The rules:

• Replace the number with the sum of the squares of its digits.
• Do the same step again on the new number. Keep repeating.
• If you ever reach 1, the number is happy.
• If you fall into a loop that never reaches 1, the number is not happy.

Let us try 19. First 1*1 + 9*9 = 1 + 81 = 82. Then 8*8 + 2*2 = 64 + 4 = 68. Then 6*6 + 8*8 = 36 + 64 = 100. Then 1 + 0 + 0 = 1. We reached 1. So 19 is happy.

Input:  n = 19
Output: true

Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

The danger is the loop. Some numbers never reach 1. They keep cycling through the same set of numbers forever. So we need a way to notice when that happens.

Here is the chain of steps for 19. Each box is the next sum of squared digits.

🐢 Approach 1: Remember Numbers in a Seen-Set (Brute Force)

The idea:

• Keep a record of every number you have already produced.
• Put each new number into a set.
• A set stores values and tells you instantly if a value is already inside.

How it works:

• Compute the next number, then check the set.
• If it is 1, the answer is yes.
• If it is already in the set, you are in a loop, so the answer is no.
• If neither, add it to the set and continue.

Why it is weak:

• It stores every number it visits.
• That is extra memory you do not actually need.
• It is correct and clear, but not the tightest answer.

Here is the seen-set code:

def is_happy(n):
    seen = set()

    while n not in seen:
        if n == 1:
            return True
        seen.add(n)
        n = sum(int(ch) ** 2 for ch in str(n))

    return False

⚡ Approach 2: Fast and Slow Pointers (Best)

The idea in one line: treat the chain of numbers as a path, and detect a loop with two walkers instead of a set.

What this builds on:

• If the number is not happy, the chain of numbers eventually loops.
• Spotting a loop in a path is a classic move called Floyd’s cycle detection.
• It is also called the fast and slow pointer method.

How it works:

• Run two walkers over the chain. One step means one round of squaring the digits.
• The slow walker takes one step each round. The fast walker takes two.
• If the chain reaches 1, the fast walker hits 1 first. The answer is yes.
• If there is a loop, the fast walker laps around and meets the slow walker. If they meet at a value that is not 1, the answer is no.

Why it is fast:

• It stores nothing. It keeps only two running numbers.
• So the space drops to O(1).

This is the chain seen as a path with a loop, and the two walkers chasing each other.

Steps to Solve

1. Write a helper that takes a number and returns the sum of the squares of its digits.
2. Set the slow walker to n. Set the fast walker to one step ahead of n.
3. Move slow by one step and fast by two steps each round.
4. Stop when fast reaches 1 or when fast meets slow.
5. If the meeting value is 1, return true. Otherwise return false.

#include <stdio.h>

// sum of squares of the digits of n
int next(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;   // last digit
        sum += d * d;     // add its square
        n /= 10;          // drop the last digit
    }
    return sum;
}

int isHappy(int n) {
    int slow = n;
    int fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);        // one step
        fast = next(next(fast));  // two steps
    }
    return fast == 1;             // reached 1 means happy
}

int main(void) {
    int n = 19;
    printf("%s\n", isHappy(n) ? "true" : "false");
    return 0;
}

true

#include <iostream>
using namespace std;

// sum of squares of the digits of n
int next(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;   // last digit
        sum += d * d;     // add its square
        n /= 10;          // drop the last digit
    }
    return sum;
}

bool isHappy(int n) {
    int slow = n;
    int fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);        // one step
        fast = next(next(fast));  // two steps
    }
    return fast == 1;             // reached 1 means happy
}

int main() {
    int n = 19;
    cout << (isHappy(n) ? "true" : "false") << endl;
    return 0;
}

true

public class HappyNumber {
    // sum of squares of the digits of n
    static int next(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;   // last digit
            sum += d * d;     // add its square
            n /= 10;          // drop the last digit
        }
        return sum;
    }

    static boolean isHappy(int n) {
        int slow = n;
        int fast = next(n);
        while (fast != 1 && slow != fast) {
            slow = next(slow);        // one step
            fast = next(next(fast));  // two steps
        }
        return fast == 1;             // reached 1 means happy
    }

    public static void main(String[] args) {
        int n = 19;
        System.out.println(isHappy(n) ? "true" : "false");
    }
}

true

def next_num(n):
    total = 0
    while n > 0:
        d = n % 10       # last digit
        total += d * d   # add its square
        n //= 10         # drop the last digit
    return total


def is_happy(n):
    slow = n
    fast = next_num(n)
    while fast != 1 and slow != fast:
        slow = next_num(slow)             # one step
        fast = next_num(next_num(fast))   # two steps
    return fast == 1                      # reached 1 means happy


n = 19
print("true" if is_happy(n) else "false")

true

function nextNum(n) {
  let total = 0;
  while (n > 0) {
    const d = n % 10;   // last digit
    total += d * d;     // add its square
    n = Math.floor(n / 10); // drop the last digit
  }
  return total;
}

function isHappy(n) {
  let slow = n;
  let fast = nextNum(n);
  while (fast !== 1 && slow !== fast) {
    slow = nextNum(slow);             // one step
    fast = nextNum(nextNum(fast));    // two steps
  }
  return fast === 1;                  // reached 1 means happy
}

const n = 19;
console.log(isHappy(n) ? "true" : "false");

true

Let us walk through the Python version line by line. The helper comes first.

def next_num(n):
    total = 0
    while n > 0:
        d = n % 10
        total += d * d
        n //= 10
    return total

n % 10 gives the last digit. We use the remainder after dividing by ten. So for 82 it gives 2. We square that digit and add it to total. Then n //= 10 does integer division by ten. That chops off the last digit. So 82 becomes 8. The loop keeps going until n reaches 0. At the end total holds the sum of the squares of all the digits.

slow = n
fast = next_num(n)

The slow walker starts at the original number. The fast walker starts one step ahead. We put fast ahead on purpose. If both started at the same spot, the loop test slow != fast would be true right away and we would stop too early.

while fast != 1 and slow != fast:
    slow = next_num(slow)
    fast = next_num(next_num(fast))

Each round, slow moves one step. Fast moves two steps. The loop runs while fast has not reached 1 and the two walkers have not met. If the number is happy, fast reaches 1 and the loop ends. If the number is not happy, fast catches slow inside the cycle and the loop ends.

return fast == 1

After the loop we check why it ended. If fast is 1, the chain reached one, so the number is happy. Otherwise they met inside a loop, so the answer is false.

⏱️ Time and Space Complexity

Both approaches run in about the same time. The numbers shrink fast and settle into a small range, so the work stays bounded. The real difference is memory. The seen-set stores every number it visits, so it uses extra space. The two-pointer method stores only two numbers, so its space is O(1). That is why the pointer method is the cleaner answer.

🧩 Key Takeaways

• ✅ Replace the number with the sum of the squares of its digits, again and again.
• ✅ Reaching 1 means the number is happy. Falling into a loop means it is not.
• ✅ A seen-set spots the loop by remembering numbers it has already produced.
• ✅ Fast and slow pointers spot the same loop using no extra memory.
• ✅ The chain of numbers is really a path that either ends at 1 or cycles forever.

🚀 What’s Next?

• Pow(x, n)
• Reverse Integer