Happy Number (Cycle Detection on a Number Sequence)

• Happy number reaches 1 when you repeatedly replace it with the sum of the squares of its digits.
• Unhappy number enters a repeating cycle that never includes 1.
• No third possibility exists because the values stay bounded and must eventually repeat.
• Floyd's cycle detection uses a slow pointer (one step) and fast pointer (two steps) with O(1) space.
• HashSet alternative stores every intermediate value and stops when a repeat or 1 appears.
• Digit extraction uses modulo for the last digit and integer division to strip it.

What is the Happy Number problem?

A happy number is defined by repeatedly replacing a number with the sum of the squares of its digits. If this process eventually reaches 1, the number is happy. If it enters a cycle that never includes 1, the number is unhappy. The task is to determine whether a given number is happy.

package com.bank.service;

public class AccountCodeValidator {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = digitSquareSum(n);
        while (fast != 1 && slow != fast) {
            slow = digitSquareSum(slow);
            fast = digitSquareSum(digitSquareSum(fast));
        }
        return fast == 1;
    }

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

Why does this always reach 1 or cycle?

For any number with d digits, the maximum sum of squared digits is 9^2 * d = 81d. A 3-digit number can produce at most 243. A 4-digit number at most 324. So any number above 999 quickly drops below 1000, and once below 1000, the sequence stays in a finite range. In a finite range, the sequence must eventually revisit a value, creating either a cycle through 1 (happy) or a cycle not through 1 (unhappy).

Example: n = 19 (happy)
  19 → 1^2 + 9^2 = 82
  82 → 8^2 + 2^2 = 68
  68 → 6^2 + 8^2 = 100
  100 → 1^2 + 0^2 + 0^2 = 1 → Happy!

Example: n = 2 (unhappy)
  2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → cycle!

How does Floyd's tortoise and hare work here?

The slow pointer applies the transformation once per step. The fast pointer applies it twice per step. If the sequence reaches 1, the fast pointer will hit 1 first (or at the same time). If the sequence cycles, the slow and fast pointers will meet inside the cycle at a value other than 1.

// Floyd's: slow moves 1 step, fast moves 2 steps
int slow = n;
int fast = digitSquareSum(n);
while (fast != 1 && slow != fast) {
    slow = digitSquareSum(slow);               // 1 step
    fast = digitSquareSum(digitSquareSum(fast)); // 2 steps
}
// If fast == 1 → happy; if slow == fast → cycle → unhappy

What is the HashSet alternative?

Instead of two pointers, store every intermediate value in a HashSet. If you see 1, the number is happy. If you see a value already in the set, the number is unhappy.

public boolean isHappyHashSet(int n) {
    java.util.Set<Integer> seen = new java.util.HashSet<>();
    while (n != 1 && seen.add(n)) {
        n = digitSquareSum(n);
    }
    return n == 1;
}

| Aspect | Floyd's | HashSet |
|--------|---------|--------|
| Space | O(1) | O(k) where k is cycle length |
| Code simplicity | Slightly harder | Simpler |
| Speed | Same | Same |
| Interview preference | Shows depth | Shows correctness |

How does the digit extraction work?

The modulo operator n % 10 extracts the last digit. Integer division n / 10 strips it away. Repeat until n is 0. Square each extracted digit and add to a running sum.

private int digitSquareSum(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;      // extract last digit
        sum += digit * digit;     // square and accumulate
        n /= 10;                  // strip last digit
    }
    return sum;
}

// Example: n = 82
// digit = 2, sum = 4, n = 8
// digit = 8, sum = 68, n = 0
// return 68

What are edge cases?

• n = 1: already 1, return true immediately.
• n = 0: digitSquareSum(0) = 0, which cycles forever, so 0 is unhappy.
• Large numbers: quickly drop into the small-number range and behave the same.
• Negative numbers: typically the problem only considers positive integers.

// Edge case: n = 1
// fast = digitSquareSum(1) = 1 → return true immediately

// Edge case: n = 0
// digitSquareSum(0) = 0, slow=0, fast=0, slow==fast → unhappy

What are common mistakes?

The first mistake is not handling the initial case where n is already 1. The second mistake is infinite looping because neither cycle detection nor a HashSet is used. The third mistake is using n * n instead of squaring each digit individually.

// WRONG: squares the whole number instead of each digit
sum = n * n;  // this is not digit-square-sum!

// CORRECT: square each digit separately
while (n > 0) {
    int digit = n % 10;
    sum += digit * digit;
    n /= 10;
}

How is this connected to cycle detection in linked lists?

The sequence of digit-square-sum values can be thought of as a linked list where each value points to the next. The happy number problem is detecting whether the "linked list" ends at 1 (no cycle through 1) or cycles without reaching 1. Floyd's algorithm applies identically, which is why this problem appears in the graph/cycle-detection topic.

What should a senior engineer know?

The key insight interviewers look for is recognizing that a numeric sequence problem is really a cycle-detection problem in disguise. The two-pointer technique from linked lists applies directly. The O(1) space approach demonstrates understanding that the same mathematical structure (a function that maps values to values) admits the same algorithmic tools regardless of whether the values are list nodes or integers.

At the National Bank of India, Rajesh used this as a lightweight checksum validation for legacy account codes. A code was accepted only if the digit-folding process reached 1, and the two-pointer validator ensured no code could cause an infinite validation loop, which mattered when processing thousands of codes in batch.