Happy Number

📋

Problem

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?

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

Edge cases: 1 → true (smallest happy number)2 → false (enters cycle)7 → true (happy number)

</>

IDE

def isHappy(n: int) -> bool:public boolean isHappy(int n)bool isHappy(int n)function isHappy(n)

def isHappy(n: int) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isHappy(int n) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isHappy(int n) {
    // Write your solution here
    return false;
}

function isHappy(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for input 2Missing cycle detection causes infinite loop or incorrect true return.✅ Implement cycle detection using a set or fast-slow pointers to detect repeated numbers.

Wrong: false for input 1No base case handling for n=1, causing unnecessary processing and wrong output.✅ Add early return if n == 1 to return true immediately.

Wrong: true for input 4Fails to detect cycle in sequence, incorrectly assuming happiness.✅ Use Floyd's cycle detection or a set to detect cycles and return false if cycle found without 1.

Wrong: true for input 3Assuming all numbers eventually reach 1 without cycle detection.✅ Implement cycle detection to identify non-happy numbers that cycle endlessly.

Wrong: TLE on large input 99999Using set-based cycle detection with large input causing time limit exceeded.✅ Switch to Floyd's fast-slow pointer cycle detection to reduce time and space complexity.

✓

Test Cases

Focus on handling smallest inputs and detecting cycles correctly.

Consider known cycle patterns and avoid greedy heuristics.

Optimize your cycle detection to run efficiently on large inputs.

t1_01basic

Input19

Expectedtrue

⏱ Performance - must finish in 2000ms

19 leads to 1 through sum of squares sequence: 19 -> 82 -> 68 -> 100 -> 1

💡 Try simulating the sum of squares of digits repeatedly.

💡 Check if the sequence reaches 1 or cycles back to a previous number.

💡 Use a set or fast-slow pointers to detect cycles and confirm if 1 is reached.

Why it failed: Incorrect output means cycle detection or sum of squares calculation is wrong. Fix by correctly computing sum of squares and detecting cycles properly.

✓ Correctly identifies happy numbers using cycle detection.

t1_02basic

Input7

Expectedtrue

⏱ Performance - must finish in 2000ms

7 leads to 1 through sequence: 7 -> 49 -> 97 -> 130 -> 10 -> 1

💡 Try following the sum of squares sequence for 7.

💡 Detect if the sequence reaches 1 or loops endlessly.

💡 Implement cycle detection to confirm 7 is happy.

Why it failed: Fails if cycle detection misses or sum of squares calculation is incorrect. Fix by ensuring sum of squares and cycle detection logic are correct.

✓ Correctly detects 7 as a happy number.

t2_01edge

Input1

Expectedtrue

⏱ Performance - must finish in 2000ms

1 is the smallest happy number by definition.

💡 Check the base case where n is already 1.

💡 Ensure your code returns true immediately if input is 1.

💡 Add a condition to return true if n == 1 before any processing.

Why it failed: Fails if code does not handle n=1 as a base case and continues processing. Fix by adding early return for n == 1.

✓ Correctly handles the smallest happy number base case.

t2_02edge

Input2

Expectedfalse

⏱ Performance - must finish in 2000ms

2 enters a cycle and never reaches 1, so it is not happy.

💡 Try detecting cycles that do not include 1.

💡 Use a set or fast-slow pointers to detect repeated numbers.

💡 Return false if a cycle is detected without reaching 1.

Why it failed: Fails if cycle detection is missing or incorrect, causing infinite loop or wrong true output. Fix by implementing proper cycle detection.

✓ Correctly detects non-happy numbers that cycle endlessly.

t2_03edge

Input100000

Expectedtrue

⏱ Performance - must finish in 2000ms

100000 reduces to 1 through sum of squares sequence: 100000 -> 1

💡 Handle numbers with trailing zeros correctly in sum of squares calculation.

💡 Ensure digits are extracted properly even if zeros are present.

💡 Sum of squares for 100000 is 1, so return true immediately.

Why it failed: Fails if digit extraction or sum of squares calculation ignores zeros or miscalculates. Fix by correctly processing all digits including zeros.

✓ Correctly processes numbers with trailing zeros.

t3_01corner

Input4

Expectedfalse

⏱ Performance - must finish in 2000ms

4 enters a known cycle (4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4) and is not happy.

💡 Beware of cycles that do not include 1 but repeat numbers.

💡 Use Floyd's cycle detection (fast and slow pointers) to detect cycles efficiently.

💡 Return false if cycle detected without reaching 1.

Why it failed: Fails if cycle detection is naive or missing, causing infinite loop or wrong true output. Fix by implementing fast-slow pointer cycle detection.

✓ Correctly detects cycles and returns false for non-happy numbers.

t3_02corner

Input19

Expectedtrue

⏱ Performance - must finish in 2000ms

Test to catch greedy approach that assumes any number with digit 1 is happy; 19 is happy but must be confirmed by full sequence.

💡 Do not assume happiness based on digits alone; simulate the sequence.

💡 Check the entire sequence until 1 or cycle is found.

💡 Use cycle detection rather than digit heuristics.

Why it failed: Fails if greedy digit-based heuristic is used instead of full sequence simulation. Fix by simulating sum of squares sequence fully.

✓ Correctly simulates sequence rather than relying on digit heuristics.

t3_03corner

Input3

Expectedfalse

⏱ Performance - must finish in 2000ms

3 enters a cycle and is not happy; tests confusion between 0/1 and unbounded sequences.

💡 Distinguish between sequences that end at 1 and those that cycle endlessly.

💡 Use cycle detection to avoid infinite loops.

💡 Return false if cycle detected without reaching 1.

Why it failed: Fails if code assumes unbounded sequences always reach 1 or misses cycle detection. Fix by implementing cycle detection properly.

✓ Correctly distinguishes happy and non-happy numbers with cycle detection.

t4_01performance

Input99999

Expectednull

⏱ Performance - must finish in 2000ms

Input n=99999 tests performance of cycle detection algorithm with O(k * log n) complexity; must complete within 2 seconds.

💡 Optimize cycle detection using fast and slow pointers to achieve O(1) space.

💡 Avoid storing all seen numbers to reduce memory overhead.

💡 Implement efficient digit extraction and sum of squares calculation.

Why it failed: TLE occurs if brute force set-based cycle detection is used with large input. Fix by using Floyd's fast-slow pointer cycle detection to reduce time and space complexity.

✓ Algorithm runs within time limits using efficient cycle detection.

Practice

1. Consider the following code that detects a cycle by marking nodes as visited. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2), what is the output of hasCycle(node1)?

easy

A. true

B. false

C. null

D. Runtime error due to infinite loop

Solution

1. Step 1: Trace the traversal and marking of nodes

   Start at node1 (visited=false), mark visited=true, move to node2. Repeat for node2 and node3. When reaching node4, mark visited=true and move to node2 again, which is already visited.

2. Step 2: Detect cycle when revisiting node2

   Since node2.visited is true, the function returns true indicating a cycle.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detected correctly by visited flag [OK]

Hint: Cycle detected when revisiting a marked node [OK]

Common Mistakes:

• Assuming no cycle due to missing pointer update
• Confusing return values

2. You are given a singly linked list and need to find the node that is exactly in the middle of the list. Which approach guarantees finding the middle node in a single pass with constant extra space?

easy

A. Store all nodes in an array, then access the middle index directly.

B. Traverse the list twice: first to count nodes, second to reach the middle node.

C. Use two pointers: move one pointer twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle.

D. Use a recursive approach to reach the end and count backwards to the middle.

Solution

1. Step 1: Understand the problem constraints

   The goal is to find the middle node in a single pass and O(1) space.

2. Step 2: Identify the approach that uses two pointers

   Using a slow pointer moving one step and a fast pointer moving two steps ensures when fast reaches the end, slow is at the middle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer technique is classic for single-pass middle node [OK]

Hint: Two pointers with different speeds find middle in one pass [OK]

Common Mistakes:

• Thinking counting then traversing is single pass
• Using extra space unnecessarily
• Recursion adds overhead and is not optimal

3. Given the following code, what is the output when calling nth_from_end(head, 3) where head is a linked list with values [5, 10, 15, 20]?

easy

A. 5

B. 15

C. 20

D. 10

Solution

1. Step 1: Trace stack contents after traversal

   Stack after pushing nodes: [5, 10, 15, 20]

2. Step 2: Pop n-1=2 times and then pop once more for value

   Pop 1: 20, Pop 2: 15, final pop returns 10 which is the 3rd from end

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   3rd from end in [5,10,15,20] is 10 [OK]

Hint: Stack top is last node; pop n times to get nth from end [OK]

Common Mistakes:

• Off-by-one popping
• Returning node instead of value
• Confusing index from front vs end

4. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here

5. 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