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. Given the following code for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

2. Identify the bug in the following code snippet for detecting and returning the cycle length in a linked list.

medium

A. Line 11: The length counting loop should start with length = 0 instead of 1.

B. Line 6: slow pointer should move two steps instead of one.

C. Line 7: fast pointer should move one step instead of two.

D. Line 4: The condition should check both fast and fast.next to avoid null pointer errors.

Solution

1. Step 1: Check loop condition for pointer safety

   The loop condition only checks if fast is not null, but fast.next may be null causing runtime error on fast.next.next.

2. Step 2: Confirm other lines are correct

   Slow moves one step, fast moves two steps correctly; length counting starts at 1 correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing fast.next check causes null pointer dereference [OK]

Hint: Always check fast and fast.next before advancing fast by two steps [OK]

Common Mistakes:

• Forgetting fast.next check
• Off-by-one in length counting
• Swapping slow and fast pointer steps

3. The following code attempts to remove the nth node from the end of a singly linked list. Identify the line containing the subtle bug that causes incorrect behavior when removing the head node.

medium

A. Line 12: recurse(head)

B. Line 9: node.next = node.next.next

C. Line 3: def recurse(node):

D. Line 13: return head

Solution

1. Step 1: Understand dummy node role

   Dummy node is needed to handle removal of the head node safely.

2. Step 2: Identify missing dummy usage

   Calling recurse on head directly skips dummy, so removing head node breaks list or returns wrong head.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dummy node causes incorrect removal of head [OK]

Hint: Always use dummy node to handle head removal edge case [OK]

Common Mistakes:

• Not using dummy node causing null pointer or wrong head
• Incorrectly unlinking nodes causing list corruption
• Off-by-one errors in recursion index

4. What is the space complexity of the recursive reorderList implementation shown below, considering a linked list of length n?

medium

A. O(log n) -- recursion divides list in halves

B. O(1) -- only constant extra pointers used

C. O(n) -- recursion stack grows linearly with list length

D. O(n^2) -- nested recursive calls cause quadratic space

Solution

1. Step 1: Analyze recursion depth

   Each recursive call moves one node forward, so recursion depth is n.

2. Step 2: Determine space usage

   Each call adds a stack frame, so total auxiliary space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack grows linearly with input size [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming recursion is O(1) space
• Confusing recursion with divide-and-conquer
• Thinking nested calls multiply space

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