Check If N and Its Double Exist

Check If N and Its Double Exist

What is this problem about?

The "Check If N and Its Double Exist interview question" asks you to determine if an array contains two different indices i and j such that arr[i] == 2 * arr[j]. For example, in [10, 2, 5, 3], both 10 and 5 exist ($10 = 2 imes 5$), so the condition is met.

Why is this asked in interviews?

Companies like Meta, Amazon, and Google use the "Check If N and Its Double Exist coding problem" as a warm-up. It tests a candidate's ability to use a "Hash Table interview pattern" to solve search problems in $O(N)$ time. It also requires careful handling of the number zero and non-integer divisions.

Algorithmic pattern used

This problem is best solved using a Hash Set for Lookups.

1. Iterate: Loop through every number x in the array.
2. Check:
   • Does the set contain 2 * x?
   • Does the set contain x / 2 (if $x$ is even)?
3. Store: Add x to the set.
4. Order: It's important to check the conditions before adding the current element to the set to ensure you don't match an element with itself (unless there are two zeros in the input).

Example explanation

Array: [7, 1, 14, 11]

1. Read 7: Set is empty. Add 7.
2. Read 1: Check for 2 or 0.5. No. Add 1.
3. Read 14: Check for 28 or 7. 7 is in the set! Result: True.

Common mistakes candidates make

• Integer Division: Checking for x / 2 without verifying if $x$ is even (e.g., if $x=7$, $x/2$ might be 3 in integer math, leading to a false positive if 3 is in the set).
• Matching Self: Not ensuring $i eq j$. If using a set, checking the set before adding the current element handles this naturally.
• Nested Loops: Using $O(N^2)$ to check every pair, which is acceptable for small arrays but less efficient than the $O(N)$ set approach.

Interview preparation tip

Hash Tables/Sets are the most common tool for "existence" problems. Practice identifying when a problem requires finding a relationship between two elements—a set is almost always the optimal choice.