How to Solve Check If N and Its Double Exist

For Check If N and Its Double Exist, the cleanest solution is a single array scan with a hash set of previously seen values. At each number, check whether its double has appeared already, or whether it is even and its half has appeared already. That directly captures the pair condition without sorting, extra pointer logic, or comparing every pair.

Problem Statement

You are given an integer array and need to decide whether two different positions form the relation where one value is exactly twice the other. The task is not to return the pair, only to report whether such indices exist anywhere in the array. For example, in arr = [10,2,5,3], the answer is true because 10 is double 5 at a different index.

A second example shows the opposite case: arr = [3,1,7,11] returns false because no value is paired with its double anywhere else in the array. The input size is small enough for brute force to pass, but the intended pattern is faster: scan the array, remember earlier numbers, and detect a matching double or half as soon as it appears.

Examples

Example 1

Input: arr = [10,2,5,3]

Output: true

For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2

Input: arr = [3,1,7,11]

Output: false

There is no i and j that satisfy the conditions.

Constraints

• 2 <= arr.length <= 500
• -103 <= arr[i] <= 103

Solution Approach

Use a seen set while scanning left to right

The core pattern for Check If N and Its Double Exist is array scanning plus hash lookup. As you iterate through arr, maintain a hash set containing values from earlier indices only. For the current number x, you want to know whether some previous value is x * 2 or whether x itself is double some previous value, which means x must be even and x / 2 must already be present.

Why checking both directions matters

Only checking whether 2 * x exists in the seen set misses cases like arr = [10,2,5,3], where 10 appears before 5. When you reach 5, you must detect that 10 was already seen. Likewise, when you reach a larger even number, checking x / 2 catches cases where the smaller value appeared first. This symmetric lookup is the exact failure mode that trips up one-sided implementations.

Stop immediately when a valid pair appears

At each index, do the lookups before inserting the current value into the set. That order prevents accidentally pairing a number with itself at the same index, which matters especially for 0 because 0 is double 0 only if there are two zero entries. If either lookup succeeds, return true immediately. If the loop finishes with no match, return false.

Complexity Analysis

The hash set approach runs in O(n) time because each array element is processed once and each lookup is O(1) on average. It uses O(n) space in the worst case to store previously seen values. This is better than the O(n^2) nested-loop check and simpler than sorting-based variants that add ordering work for a problem that only needs existence.

What Interviewers Usually Probe

• They mention storing values from indices [0, i - 1] while scanning, which points directly to a seen-set solution.
• They ask how to avoid comparing every pair, which usually means replace brute force with O(1) membership checks.
• They emphasize different indices i and j, which is a clue to check before inserting the current value into the hash set.

Common Pitfalls or Variants

Common pitfalls

• Checking only one direction, such as whether 2 * x was seen, misses pairs where the larger number appears earlier.
• Forgetting the even-number guard before checking x / 2 can create incorrect matches for odd values.
• Adding the current number to the set before lookup can falsely treat one element as both sides of the pair, especially around 0.

Follow-up variants

• Sort the array and use binary search for each value, but the logic becomes less direct than the hash lookup pattern.
• Use a frequency map if you also want to reason explicitly about duplicates like two zeroes.
• Return the actual index pair instead of a boolean, which requires storing positions rather than only seen values.

How GhostInterview Helps

• GhostInterview identifies that Check If N and Its Double Exist is not a two-pointer-first problem and pushes the faster seen-set scan.
• GhostInterview catches the one-sided lookup bug and reminds you to test both double and half depending on order.
• GhostInterview flags the zero and same-index edge case so the implementation checks before insertion.

Topic Pages

• Array
• Hash Table
• Two Pointers
• Binary Search
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best pattern for Check If N and Its Double Exist?

The best pattern is a single pass with a hash set of previously seen numbers. For each value x, check whether 2 * x is already seen or whether x is even and x / 2 is already seen.

Why is the hash set solution better than sorting here?

Sorting can work, but it adds extra work to a problem that only asks whether any valid pair exists. The hash set scan matches the condition directly and finishes in linear time on average.

Why do we check before inserting the current number?

That preserves the requirement that the two values come from different indices. It also avoids incorrect self-matching when the current value could satisfy the relation with itself, especially for 0.

Do we really need to check x / 2 as well as 2 * x?

Yes, because the array order is arbitrary. In arr = [10,2,5,3], the larger value 10 appears before 5, so checking only doubles would miss the valid pair.

How should I think about the zero case in this problem?

Zero only forms a valid answer when there are at least two zeroes at different indices. The check-before-insert order handles this cleanly because the second zero will find the first one already in the set.