Happy Number

🎯

Happy Number

easyTWO_POINTERAmazonGoogleBloomberg

Imagine a number game where you repeatedly replace a number by the sum of the squares of its digits. Will you eventually reach 1, or get stuck in a loop forever?

💡 This problem involves detecting cycles in a sequence generated by repeatedly applying a function to a number. Beginners often struggle because the sequence is implicit (not stored explicitly) and cycles are not obvious without careful detection.

📋

Problem Statement

Given a positive integer n, determine if it is a happy number. A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Return true if n is a happy number, and false if not.

1 ≤ n ≤ 10^5

💡

Example

Input"19"

Outputtrue

19 → 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1, so 19 is happy.

• 1 → true (smallest happy number)
• 2 → false (enters cycle)
• 7 → true (happy number)
• 100000 → true (large number with trailing zeros)

⚠️

Common Mistakes

Not detecting cycles properly, leading to infinite loops

Code runs forever or times out

✅ Use a set or fast-slow pointers to detect cycles

Incorrectly computing sum of squares of digits

Wrong results or failure on test cases

✅ Carefully extract digits using modulo and integer division

Using recursion without cycle detection

Stack overflow or infinite recursion

✅ Add cycle detection or convert to iterative approach

Assuming all numbers eventually reach 1 without proof

Incorrectly returning true for unhappy numbers

✅ Implement cycle detection to handle loops

Using extra space unnecessarily when fast-slow pointer suffices

Less optimal solution with higher memory usage

✅ Learn and implement Floyd's cycle detection for space optimization

🧠

Brute Force (Using a Set to Detect Cycles)

💡 This approach introduces the fundamental idea of cycle detection by storing all previously seen numbers. It is simple and intuitive, helping beginners understand why cycles occur and how to detect them.

Intuition

Repeatedly compute the sum of squares of digits and store each result. If we reach 1, the number is happy. If we see a number again, a cycle exists and the number is not happy.

Algorithm

1. Initialize an empty set to store seen numbers.
2. While the current number is not 1 and not in the set:
3. Add the current number to the set.
4. Replace the current number with the sum of the squares of its digits.
5. If the loop ends with number 1, return true; otherwise, return false.

💡 The main challenge is to realize that repeating numbers indicate a cycle, and storing them helps detect this.

</>

Code

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)
    return n == 1

# Driver code
if __name__ == '__main__':
    print(isHappy(19))  # Expected: True
    print(isHappy(2))   # Expected: False

Line Notes

def get_next(number):Helper function to compute sum of squares of digits

while number > 0:Extract digits one by one from the number

seen = set()Store all numbers seen so far to detect cycles

while n != 1 and n not in seen:Loop until we find 1 or detect a cycle

import java.util.HashSet;
import java.util.Set;

public class HappyNumber {
    public static boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }

    private static int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // true
        System.out.println(isHappy(2));  // false
    }
}

Line Notes

Set<Integer> seen = new HashSet<>();Keep track of numbers to detect cycles

while (n != 1 && !seen.contains(n)) {Continue until 1 is found or cycle detected

seen.add(n);Add current number to the set

int digit = number % 10;Extract last digit for sum of squares

#include <iostream>
#include <unordered_set>

using namespace std;

int getNext(int number) {
    int totalSum = 0;
    while (number > 0) {
        int digit = number % 10;
        totalSum += digit * digit;
        number /= 10;
    }
    return totalSum;
}

bool isHappy(int n) {
    unordered_set<int> seen;
    while (n != 1 && seen.find(n) == seen.end()) {
        seen.insert(n);
        n = getNext(n);
    }
    return n == 1;
}

int main() {
    cout << boolalpha << isHappy(19) << endl; // true
    cout << boolalpha << isHappy(2) << endl;  // false
    return 0;
}

Line Notes

unordered_set<int> seen;Track visited numbers to detect cycles

while (n != 1 && seen.find(n) == seen.end()) {Loop until 1 or cycle detected

seen.insert(n);Mark current number as visited

int digit = number % 10;Extract digits for sum of squares

function getNext(number) {
    let totalSum = 0;
    while (number > 0) {
        let digit = number % 10;
        totalSum += digit * digit;
        number = Math.floor(number / 10);
    }
    return totalSum;
}

function isHappy(n) {
    const seen = new Set();
    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n === 1;
}

// Test cases
console.log(isHappy(19)); // true
console.log(isHappy(2));  // false

Line Notes

const seen = new Set();Store numbers to detect cycles

while (n !== 1 && !seen.has(n)) {Loop until 1 or cycle detected

seen.add(n);Add current number to the set

let digit = number % 10;Extract digits for sum of squares

⏱

Complexity

TimeO(k * log n) where k is number of iterations until cycle or 1

SpaceO(k) for storing seen numbers

Each iteration computes sum of squares in O(log n) digits, and we store each unique number until cycle or 1 is found.

💡 For n=19, about 5-6 iterations happen, so roughly 30 operations total, which is efficient enough for small inputs.

Interview Verdict: Accepted

This approach is simple and works well for the input constraints, making it a good starting point in interviews.

🧠

Fast and Slow Pointer (Floyd's Cycle Detection)

💡 This approach uses two pointers moving at different speeds to detect cycles without extra space, demonstrating a classic cycle detection technique useful in many problems.

Intuition

If a cycle exists, a fast pointer moving twice as fast as a slow pointer will eventually meet the slow pointer inside the cycle. If the sequence reaches 1, no cycle exists.

Algorithm

1. Initialize slow and fast pointers to the starting number.
2. Move slow pointer one step (sum of squares) and fast pointer two steps repeatedly.
3. If fast pointer reaches 1, return true (happy number).
4. If slow and fast pointers meet at a number other than 1, return false (cycle detected).

💡 The key insight is that meeting pointers means a cycle, and reaching 1 means success.

</>

Code

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    slow = n
    fast = get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1

# Driver code
if __name__ == '__main__':
    print(isHappy(19))  # Expected: True
    print(isHappy(2))   # Expected: False

Line Notes

slow = nInitialize slow pointer at start

fast = get_next(n)Initialize fast pointer one step ahead

while fast != 1 and slow != fast:Loop until fast reaches 1 or pointers meet

fast = get_next(get_next(fast))Move fast pointer two steps to detect cycle

public class HappyNumber {
    public static boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }

    private static int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // true
        System.out.println(isHappy(2));  // false
    }
}

Line Notes

int slow = n;Slow pointer starts at initial number

int fast = getNext(n);Fast pointer starts one step ahead

while (fast != 1 && slow != fast) {Loop until cycle detected or happy number found

fast = getNext(getNext(fast));Fast pointer moves two steps to catch cycle

#include <iostream>

using namespace std;

int getNext(int number) {
    int totalSum = 0;
    while (number > 0) {
        int digit = number % 10;
        totalSum += digit * digit;
        number /= 10;
    }
    return totalSum;
}

bool isHappy(int n) {
    int slow = n;
    int fast = getNext(n);
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}

int main() {
    cout << boolalpha << isHappy(19) << endl; // true
    cout << boolalpha << isHappy(2) << endl;  // false
    return 0;
}

Line Notes

int slow = n;Initialize slow pointer at start

int fast = getNext(n);Initialize fast pointer one step ahead

while (fast != 1 && slow != fast) {Loop until cycle or happy number found

fast = getNext(getNext(fast));Fast pointer moves two steps to detect cycle

function getNext(number) {
    let totalSum = 0;
    while (number > 0) {
        let digit = number % 10;
        totalSum += digit * digit;
        number = Math.floor(number / 10);
    }
    return totalSum;
}

function isHappy(n) {
    let slow = n;
    let fast = getNext(n);
    while (fast !== 1 && slow !== fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast === 1;
}

// Test cases
console.log(isHappy(19)); // true
console.log(isHappy(2));  // false

Line Notes

let slow = n;Slow pointer starts at initial number

let fast = getNext(n);Fast pointer starts one step ahead

while (fast !== 1 && slow !== fast) {Loop until cycle detected or happy number found

fast = getNext(getNext(fast));Fast pointer moves two steps to catch cycle

⏱

Complexity

TimeO(k * log n) where k is iterations until cycle or 1

SpaceO(1) constant space

Each iteration computes sum of squares in O(log n) digits, but no extra memory is used for cycle detection.

💡 This approach is more memory efficient than brute force, especially for large inputs.

Interview Verdict: Accepted

This is the optimal approach for cycle detection in this problem and is preferred in interviews.

🧠

Mathematical Insight with Known Cycle Detection

💡 This approach uses known facts about cycles in happy numbers to shortcut detection, useful for optimization and demonstrating domain knowledge.

Intuition

All unhappy numbers eventually enter a known cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. If the sequence hits any number in this cycle, it is not happy.

Algorithm

1. Define a set of known cycle numbers for unhappy sequences.
2. Iterate computing sum of squares of digits.
3. If the number becomes 1, return true.
4. If the number is in the known cycle set, return false.

💡 This approach trades memory for speed by using a fixed set of cycle numbers.

</>

Code

def isHappy(n: int) -> bool:
    cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}

    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    while n != 1 and n not in cycle_set:
        n = get_next(n)
    return n == 1

# Driver code
if __name__ == '__main__':
    print(isHappy(19))  # Expected: True
    print(isHappy(2))   # Expected: False

Line Notes

cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}Known unhappy cycle numbers to detect loops quickly

while n != 1 and n not in cycle_set:Loop until happy or known cycle detected

def get_next(number):Helper to compute sum of squares of digits

return n == 1Return true if happy, false if cycle detected

import java.util.Set;
import java.util.HashSet;

public class HappyNumber {
    private static final Set<Integer> cycleSet = new HashSet<>();
    static {
        cycleSet.add(4); cycleSet.add(16); cycleSet.add(37); cycleSet.add(58);
        cycleSet.add(89); cycleSet.add(145); cycleSet.add(42); cycleSet.add(20);
    }

    public static boolean isHappy(int n) {
        while (n != 1 && !cycleSet.contains(n)) {
            n = getNext(n);
        }
        return n == 1;
    }

    private static int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // true
        System.out.println(isHappy(2));  // false
    }
}

Line Notes

private static final Set<Integer> cycleSet = new HashSet<>();Store known unhappy cycle numbers

while (n != 1 && !cycleSet.contains(n)) {Loop until happy or known cycle detected

cycleSet.add(4);Initialize cycle set with known cycle numbers

return n == 1;Return true if happy, false otherwise

#include <iostream>
#include <unordered_set>

using namespace std;

bool isHappy(int n) {
    static unordered_set<int> cycleSet = {4,16,37,58,89,145,42,20};

    auto getNext = [](int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    };

    while (n != 1 && cycleSet.find(n) == cycleSet.end()) {
        n = getNext(n);
    }
    return n == 1;
}

int main() {
    cout << boolalpha << isHappy(19) << endl; // true
    cout << boolalpha << isHappy(2) << endl;  // false
    return 0;
}

Line Notes

static unordered_set<int> cycleSet = {4,16,37,58,89,145,42,20};Known cycle numbers stored statically

while (n != 1 && cycleSet.find(n) == cycleSet.end()) {Loop until happy or cycle detected

auto getNext = [](int number) {Lambda to compute sum of squares

return n == 1;Return true if happy, false otherwise

const cycleSet = new Set([4,16,37,58,89,145,42,20]);

function getNext(number) {
    let totalSum = 0;
    while (number > 0) {
        let digit = number % 10;
        totalSum += digit * digit;
        number = Math.floor(number / 10);
    }
    return totalSum;
}

function isHappy(n) {
    while (n !== 1 && !cycleSet.has(n)) {
        n = getNext(n);
    }
    return n === 1;
}

// Test cases
console.log(isHappy(19)); // true
console.log(isHappy(2));  // false

Line Notes

const cycleSet = new Set([4,16,37,58,89,145,42,20]);Known unhappy cycle numbers for quick detection

while (n !== 1 && !cycleSet.has(n)) {Loop until happy or cycle detected

function getNext(number) {Helper to compute sum of squares

return n === 1;Return true if happy, false otherwise

⏱

Complexity

TimeO(k * log n) with small constant due to early cycle detection

SpaceO(1) constant space

Checking membership in a small fixed set is O(1), speeding up cycle detection.

💡 This approach is a practical optimization that leverages known math facts to shortcut cycle detection.

Interview Verdict: Accepted

This approach is efficient and shows domain knowledge, which can impress interviewers.

📊

All Approaches - One-Glance Tradeoffs

💡 The fast-slow pointer approach is the best balance of simplicity and efficiency, and is recommended for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Set for cycle detection)	O(k * log n)	O(k)	No	N/A	Good to mention and understand cycle detection basics
2. Fast and Slow Pointer (Floyd's Cycle Detection)	O(k * log n)	O(1)	No	N/A	Optimal approach to implement in interviews
3. Known Cycle Set Optimization	O(k * log n)	O(1)	No	N/A	Good to mention as an optimization or domain knowledge

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach using a set to detect cycles.Step 3: Explain the fast-slow pointer technique for cycle detection.Step 4: Mention the known cycle optimization if time permits.Step 5: Code the fast-slow pointer approach for optimal space.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Understanding of cycle detection, ability to optimize space, and clear explanation of tradeoffs.

Common Follow-ups

• Can you detect cycles without extra space? → Use fast and slow pointers.
• What if the input number is very large? → The sum of squares reduces number size quickly.
• Can you prove the cycle detection terminates? → Because numbers reduce to a bounded range.
• What is the time complexity? → O(k * log n), k is iterations until cycle or 1.

💡 These follow-ups test deeper understanding of cycle detection and complexity analysis.

🔍

Pattern Recognition

When to Use

1) Problem involves repeated transformation of a number or state; 2) Need to detect if process ends or loops; 3) Cycle detection is required; 4) No explicit data structure given, sequence is implicit.

Signature Phrases

repeatedly replace numbersum of squares of digitsends in 1 or loops endlessly

NOT This Pattern When

Problems that require explicit graph traversal or DP without cycle detection.

Similar Problems

Linked List Cycle - same cycle detection techniqueFind the Duplicate Number - cycle detection in arrayDetect Cycle in a Graph - general cycle detection

Practice

1. You are given a singly linked list and two integers M and N. The task is to traverse the list, skip M nodes, then delete the next N nodes, and repeat this process until the end of the list. Which algorithmic approach best guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a recursive approach that deletes nodes during the unwinding phase of recursion.

B. Use a brute force nested loop approach that for each node checks ahead to delete N nodes repeatedly.

C. Use an iterative two-pointer approach that skips M nodes and deletes N nodes in a single pass.

D. Use a dynamic programming approach to store states of nodes to decide deletion.

Solution

1. Step 1: Understand the problem constraints

   The problem requires skipping M nodes and deleting N nodes repeatedly until the list ends, which suggests a linear traversal.

2. Step 2: Evaluate approaches

   Recursive approaches add extra space due to call stack; brute force nested loops increase time complexity; dynamic programming is unnecessary as no overlapping subproblems exist. The iterative two-pointer approach efficiently traverses once, skipping and deleting nodes in O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative two-pointer approach matches optimal time and space complexity [OK]

Hint: Iterative two-pointer approach is linear and space efficient [OK]

Common Mistakes:

• Thinking recursion is optimal despite extra stack space
• Using nested loops causing O(n²) time
• Misapplying DP to a linear traversal problem

2. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency

3. Suppose the problem is modified so that after deleting N nodes, the deleted nodes can be reinserted later in the list (i.e., nodes can be reused). Which of the following changes to the algorithm is necessary to correctly handle this variant?

hard

A. Use a recursive approach to backtrack and reinsert deleted nodes at correct positions.

B. Maintain a separate data structure to store deleted nodes and reinsert them after traversal.

C. Modify the iterative approach to skip M nodes, delete N nodes, and immediately reattach deleted nodes after the next M nodes.

D. No change needed; the original iterative approach already supports node reuse.

Solution

1. Step 1: Understand node reuse requirement

   Deleted nodes must be preserved and reinserted later, so they cannot be simply discarded by pointer reassignment.

2. Step 2: Evaluate algorithm changes

   The original approach loses references to deleted nodes. To reuse, store deleted nodes externally and reinsert after traversal or at correct positions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maintaining deleted nodes separately enables controlled reinsertion [OK]

Hint: Reusing nodes requires storing them, not discarding pointers [OK]

Common Mistakes:

• Assuming original approach supports reuse
• Trying to reattach nodes immediately without storage
• Using recursion unnecessarily

4. Suppose the array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head), and you need to remove the nth node from the end. Which approach correctly adapts to this scenario?

hard

A. First detect the cycle length by traversing until you return to the start, then remove the (length - n)th node using two pointers.

B. Use the same recursive backtracking approach without changes; it works for circular lists.

C. Break the cycle by setting the last node's next to None, then apply the standard two-pointer method.

D. Use a hash set to track visited nodes and remove the nth node from the end by counting backwards.

Solution

1. Step 1: Detect cycle length

   In a circular list, length is unknown; traverse until returning to start to find length.

2. Step 2: Use two pointers with known length

   Once length is known, use two pointers with gap n+1 to remove the target node safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle length detection is necessary before removal [OK]

Hint: Must find cycle length before applying two-pointer removal [OK]

Common Mistakes:

• Applying recursion blindly on circular list causing infinite recursion
• Breaking cycle without restoring it, altering list structure
• Using hash sets unnecessarily increasing space