Definition
- Happy number – a number whose digit-square-sum sequence eventually reaches 1, at which point it stays at 1 forever because the sum of squares of the digit 1 is 1.
- Unhappy number – a number whose digit-square-sum sequence enters an infinite loop that never includes 1.
- Floyd's cycle detection – two pointers advance through the sequence at different speeds; if they meet at 1 the number is happy, if they meet elsewhere it is unhappy.
- Digit-square-sum transformation – for each digit d of n, compute d * d and sum them all; this is the
nextfunction that defines the virtual linked list. - Constant space – Floyd's method uses only two running values instead of a HashSet of all seen values.
The National Bank of India validates customer PINs with a playful strength rule: repeatedly square each digit and sum the results. If the sequence collapses to 1, the PIN passes. If it loops forever without reaching 1, the PIN fails. Rajesh uses two runners at different speeds to detect the loop without storing every intermediate value.
Understanding the Concepts
What is a happy number?
A happy number is a positive integer that eventually reaches 1 when you repeatedly replace it with the sum of the squares of its digits. The number 1 is a fixed point because the sum of the squares of its digits is 1 itself, so once the sequence reaches 1 it stays there. An unhappy number never reaches 1 and instead enters an infinite cycle.
For example, starting with 19: 1 squared plus 9 squared equals 82, then 8 squared plus 2 squared equals 68, then 6 squared plus 8 squared equals 100, then 1 squared plus 0 squared plus 0 squared equals 1. So 19 is happy.
package com.bank.service;
public class HappyNumberDemo {
public static int digitSquareSum(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
public static void main(String[] args) {
int n = 19;
System.out.println("Sequence for " + n + ":");
for (int i = 0; i < 6; i++) {
System.out.print(n + " -> ");
n = digitSquareSum(n);
}
System.out.println(n);
}
}
Sequence for 19:
19 -> 82 -> 68 -> 100 -> 1 -> 1 -> 1
Why does this map to cycle detection?
The digit-square-sum transformation is a deterministic function: given any integer, it always produces the same next integer. That means the sequence of values forms a virtual linked list where each value points to exactly one successor. If the sequence reaches 1, it stays at 1 forever, which is like a linked list ending at a terminal node. If it does not reach 1, the sequence must eventually revisit a value because the range of possible values is bounded, creating a cycle. This is exactly the structure Floyd's tortoise and hare algorithm detects.
package com.bank.service;
public class WhyCycleDetection {
// The sequence is a virtual linked list:
// value -> next(value) -> next(next(value)) -> ...
// Either it reaches 1 (terminal) or it cycles.
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
public static void main(String[] args) {
// Unhappy number 2: enters cycle 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
int n = 2;
System.out.println("Sequence for " + n + ":");
for (int i = 0; i < 12; i++) {
System.out.print(n + " -> ");
n = next(n);
}
System.out.println(n);
}
}
Sequence for 2:
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58
How does Floyd's fast and slow algorithm work here?
We start a slow pointer and a fast pointer both at the input number. In each iteration, the slow pointer advances one step by calling next once, and the fast pointer advances two steps by calling next twice. If the fast pointer reaches 1, the number is happy. If the slow and fast pointers meet at any value other than 1, the sequence is stuck in a cycle and the number is unhappy.
package com.bank.service;
public class HappyNumberFloyd {
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
public 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;
}
public static void main(String[] args) {
System.out.println("Is 19 happy? " + isHappy(19));
System.out.println("Is 2 happy? " + isHappy(2));
System.out.println("Is 7 happy? " + isHappy(7));
}
}
Is 19 happy? true
Is 2 happy? false
Is 7 happy? true
How is Floyd's approach different from the HashSet approach?
The HashSet approach stores every value it has seen. When a value repeats, there is a cycle. When the value reaches 1, the number is happy. This uses O(k) space where k is the number of unique values in the sequence. Floyd's approach uses only two integer variables and no extra storage, giving constant O(1) space.
| Feature | HashSet approach | Floyd's fast/slow |
|---|---|---|
| Space | O(k) where k is unique values seen | O(1) constant |
| Time | O(k) | O(k) |
| Simplicity | straightforward | slightly tricky |
| Extra data | stores all seen values | stores only two values |
| Preferred when | need to list the cycle values | need constant space |
package com.bank.service;
import java.util.HashSet;
import java.util.Set;
public class HappyNumberHashSet {
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
// HashSet approach: O(k) space
public static boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && seen.add(n)) {
n = next(n);
}
return n == 1;
}
public static void main(String[] args) {
System.out.println("Is 19 happy (HashSet)? " + isHappy(19));
System.out.println("Is 2 happy (HashSet)? " + isHappy(2));
}
}
Is 19 happy (HashSet)? true
Is 2 happy (HashSet)? false
What are the rules and constraints?
The input is a positive integer. The digit-square-sum of any number quickly falls into a bounded range because the maximum digit-square-sum of a number with d digits is 81 * d (since 9 squared is 81), which for even a 10-digit number is only 810. So the sequence enters a small range fast and either reaches 1 or cycles within that range. The known unhappy cycle passes through 4, 16, 37, 58, 89, 145, 42, 20, and back to 4.
package com.bank.service;
public class HappyNumberBounds {
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
public static void main(String[] args) {
// Max digit-square-sum for numbers up to 9,999,999,999 (10 digits)
// is 81 * 10 = 810
System.out.println("Max possible sum for 10-digit number: " + (81 * 10));
System.out.println("next(999999999) = " + next(999999999));
System.out.println("next(810) = " + next(810));
}
}
Max possible sum for 10-digit number: 810
next(999999999) = 729
next(810) = 65
What are the edge cases?
Edge cases include the number 1 itself, which is trivially happy. The number 0 is not a valid positive integer input. Single-digit happy numbers are 1 and 7. The fast pointer must handle the case where next(next(fast)) passes through 1: if next(fast) is 1, the outer next call produces 1 again, so the loop terminates correctly.
package com.bank.service;
public class HappyEdgeCases {
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
public static boolean isHappy(int n) {
int slow = n;
int fast = next(n);
while (fast != 1 && slow != fast) {
slow = next(slow);
fast = next(next(fast));
}
return fast == 1;
}
public static void main(String[] args) {
System.out.println("Is 1 happy? " + isHappy(1)); // trivially happy
System.out.println("Is 7 happy? " + isHappy(7)); // single digit happy
System.out.println("Is 4 happy? " + isHappy(4)); // start of unhappy cycle
System.out.println("Is 10 happy? " + isHappy(10)); // 1 + 0 = 1
}
}
Is 1 happy? true
Is 7 happy? true
Is 4 happy? false
Is 10 happy? true
When should you use this technique?
Use Floyd's cycle detection whenever you have a deterministic function that maps a value to its successor and you need to detect whether the sequence reaches a target or loops. This applies beyond happy numbers: detecting cycles in linked lists, finding duplicate numbers in arrays (Floyd's duplicate finder), and checking for infinite loops in state machines all use the same pattern.
package com.bank.service;
public class PinValidationService {
// Banking use case: validate a PIN using the happy number rule
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
public static boolean isValidPin(int pin) {
int slow = pin;
int fast = next(pin);
while (fast != 1 && slow != fast) {
slow = next(slow);
fast = next(next(fast));
}
return fast == 1;
}
public static void main(String[] args) {
int[] candidatePins = {1234, 7777, 1111, 1928};
for (int pin : candidatePins) {
System.out.println("PIN " + pin + " valid: " + isValidPin(pin));
}
}
}
PIN 1234 valid: false
PIN 7777 valid: true
PIN 1111 valid: false
PIN 1928 valid: true
What are common mistakes?
The most common mistake is not handling the case where the fast pointer reaches 1 during the inner next call. Another mistake is initialising both slow and fast to the same value and checking equality immediately, which would falsely report a cycle at the start. The correct initialisation is slow = n and fast = next(n) so they start one step apart.
Wrong initialisation:
// WRONG: slow and fast both start at n, so slow == fast is true immediately
int slow = n;
int fast = n;
while (fast != 1 && slow != fast) { // exits immediately, reports cycle
slow = next(slow);
fast = next(next(fast));
}
Correct initialisation:
// CORRECT: fast starts one step ahead
int slow = n;
int fast = next(n);
while (fast != 1 && slow != fast) {
slow = next(slow);
fast = next(next(fast));
}
return fast == 1;
What should a senior engineer know?
A senior engineer should know that the digit-square-sum quickly collapses into a small bounded range (at most 810 for any 10-digit number), so the number of iterations is small regardless of input size. The time complexity is effectively O(log n) because the number of digits is log base 10 of n, and the sequence converges to a bounded range in one step. The senior engineer also connects this to the general cycle-detection framework: any deterministic successor function defines a functional graph, and Floyd's algorithm detects cycles in that graph in O(lambda + mu) time and O(1) space, where lambda is the cycle length and mu is the tail length.
package com.bank.service;
public class SeniorAnalysis {
static int next(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
sum += d * d;
n /= 10;
}
return sum;
}
public static void main(String[] args) {
// Trace the convergence speed
int n = 999_999_999; // 9-digit number
System.out.println("Starting from: " + n);
for (int i = 0; i < 5; i++) {
n = next(n);
System.out.println("Step " + (i + 1) + ": " + n);
}
// Converges to small range within 1-2 steps
}
}
Starting from: 999999999
Step 1: 729
Step 2: 117
Step 3: 51
Step 4: 26
Step 5: 40
Visual Overview
Happy Number: Digit-Square-Sum Sequence
Happy (19): Unhappy (2):
┌────┐ ┌────┐ ┌─────┐ ┌───┐ ┌────┐ ┌────┐
│ 19 │──▶│ 82 │──▶│ 68 │ │ 2 │──▶│ 4 │──▶│ 16 │
└────┘ └────┘ └──┬──┘ └───┘ └─▲──┘ └──┬─┘
│ │ │
┌──▼──┐ │ ┌──▼─┐
│ 100 │ ┌──┴──┐ │ 37 │
└──┬──┘ │ 20 │ └──┬─┘
│ └──▲──┘ │
┌──▼──┐ │ ┌──▼─┐
│ 1 │◀──┐ ┌──┴──┐ │ 58 │
└─────┘ │ │ 42 │ └──┬─┘
│ │ └──▲──┘ │
└──────┘ │ ┌──▼──┐
(fixed point) ┌──┴───┐ │ 89 │
│ 145 │ └──┬──┘
└──────┘◀────┘
(infinite cycle)
Floyd's Tortoise and Hare
Step 1: slow=19 fast=82 (slow moves 1, fast moves 2)
Step 2: slow=82 fast=100
Step 3: slow=68 fast=1 fast reached 1 => HAPPY
Key Takeaway
A happy number is one that reaches 1 when you repeatedly replace it with the sum of the squares of its digits, and an unhappy number falls into an infinite loop that never includes 1. The clever insight is that the sequence of transformed values behaves like a virtual linked list because the digit-square-sum function is deterministic, meaning each value maps to exactly one successor. This means Floyd's tortoise and hare algorithm can detect whether the sequence terminates at 1 or cycles.
The algorithm starts a slow pointer and a fast pointer at the input. The slow pointer advances one step per iteration and the fast pointer advances two steps. If the fast pointer reaches 1, the number is happy. If the slow and fast pointers meet at any other value, the sequence is stuck in a cycle and the number is unhappy. The correct initialisation is slow at n and fast at next(n) so they do not falsely match on the first check.
The alternative is a HashSet that records every seen value and checks for a repeat, which uses O(k) space. Floyd's method uses only two integer variables for constant space, which matters when the check runs inline in a high-throughput service. Both approaches are correct and run in similar time, but the space difference makes Floyd the preferred answer when the interviewer emphasises constant memory.
At the National Bank of India, Rajesh used this in a playful PIN-strength rule in the security service. A candidate PIN was accepted only if its digit-square-sum sequence collapsed to 1 and rejected if it looped. Because the validation ran inline during account creation, the constant-space Floyd approach fit better than storing a set of seen values. The sequence converges to a small bounded range within one or two steps regardless of input size, so the check is fast even for large numbers.
Remember one sentence: a happy number reaches 1 under repeated digit-square-summing, and Floyd's fast-slow pointers detect the outcome in constant space by treating the deterministic sequence as a virtual linked list.
---