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. You are given an array of integers and need to determine if any value appears at least twice. Which approach guarantees the most efficient detection of duplicates in terms of time complexity?

easy

A. Sort the array and then scan once to check if any adjacent elements are equal.

B. Use a hash set to track seen elements and check membership while iterating once.

C. Use nested loops to compare every pair of elements for equality.

D. Use dynamic programming to build a table of duplicate occurrences.

Solution

1. Step 1: Understand the problem requirements

   The problem requires detecting duplicates efficiently in an array.

2. Step 2: Compare approaches based on time complexity

   Sorting then scanning is O(n log n), nested loops is O(n²), and dynamic programming is unnecessary here. Using a hash set allows O(n) time with O(n) space by checking membership during one pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set membership check is O(1) average, enabling linear time detection [OK]

Hint: Hash set membership check enables linear time detection [OK]

Common Mistakes:

• Confusing sorting approach as optimal
• Thinking nested loops are efficient enough
• Misapplying DP to a membership problem

2. You need to design a data structure that supports inserting elements, deleting elements, and retrieving a random element, all in average constant time. Which approach best guarantees this performance?

easy

A. Using a balanced binary search tree to maintain elements and their indices

B. Combining a hash map for element indices with an array to store elements, using a swap-delete trick on removal

C. Using a linked list for elements and a hash set for membership checks

D. Maintaining a sorted array and performing binary search for insertions and deletions

Solution

1. Step 1: Understand operation requirements

   Insert, delete, and getRandom must all be O(1) average time.

2. Step 2: Evaluate data structures

   Balanced BST or sorted array have O(log n) or worse for insert/delete. Linked list lacks O(1) random access. Hash map + array with swap-delete achieves O(1) for all operations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash map + array with swap-delete is the classic O(1) solution [OK]

Hint: Hash map + array with swap-delete enables O(1) ops [OK]

Common Mistakes:

• Thinking balanced BST gives O(1) insert/delete
• Using linked list for O(1) random access
• Assuming sorted array can do O(1) insert/delete

3. What is the time complexity of the optimal bidirectional hash map approach to check if two strings of length n are isomorphic?

medium

A. O(n) because each character is processed once with constant-time hash map operations

B. O(n²) due to nested loops checking all character pairs

C. O(n log n) due to sorting characters before mapping

D. O(1) since hash maps provide constant-time lookups

Solution

1. Step 1: Identify the main loop over string length

   The algorithm iterates once over the strings of length n, processing each character pair exactly once.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are average O(1), so total time is O(n) * O(1) = O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) [OK]

Hint: Single pass with hash maps -> O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring hash map average case

4. The following code attempts to count subarrays summing to k. Which line contains a subtle bug that causes incorrect counts for subarrays starting at index 0?

medium

A. Line 7: if prefix_sum - k in prefix_counts (wrong condition)

B. Line 5: prefix_sum += num (incorrect accumulation)

C. Line 3: prefix_counts = {} (missing initialization with {0:1})

D. Line 9: prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1 (incorrect update)

Solution

1. Step 1: Identify initialization of prefix_counts

   prefix_counts must start with {0:1} to count subarrays starting at index 0 correctly.

2. Step 2: Check other lines

   Accumulation, condition, and update lines are correct; only initialization is missing the base case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing {0:1} causes missed counts for subarrays from start [OK]

Hint: Always initialize prefix_counts with {0:1} to handle subarrays from index 0 [OK]

Common Mistakes:

• Not initializing prefix_counts with {0:1}
• Misplacing prefix_sum updates
• Incorrect condition checks

5. Suppose the input strings can contain uppercase letters and digits in addition to lowercase letters. Which modification to the optimal frequency counting approach correctly handles this scenario?

hard

A. Use a frequency array of size 62 (26 lowercase + 26 uppercase + 10 digits) and map characters accordingly.

B. Use a frequency array of size 26 and convert all characters to lowercase before counting.

C. Sort each string and use the sorted string as the hash map key.

D. Use a hash map with character counts stored as a dictionary instead of an array.

Solution

1. Step 1: Identify character set

   Input includes lowercase, uppercase, and digits, total 62 distinct characters.

2. Step 2: Adjust frequency counting

   Frequency array size must be 62, mapping each character to an index to count correctly.

3. Step 3: Evaluate alternatives

   Converting to lowercase loses information, sorting is slower, dictionary counts add overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency array size matches character set size [OK]

Hint: Frequency array size must cover all possible characters [OK]

Common Mistakes:

• Lowercasing loses info
• Using smaller array size
• Assuming sorting is always best