1346. Check If N and Its Double Exist - Detailed Explanation

Problem Statement

You are given an array of integers, arr. The task is to determine whether there exists two distinct indices i and j such that:

$[ \text{arr}[i] = 2 \times \text{arr}[j] ]$

Return true if such a pair exists; otherwise, return false.

Input: [10, 2, 5, 3]
Output: true
Explanation:
For this array, 10 is exactly double 5. Therefore, the condition is satisfied.

Input: [3, 1, 7, 11]
Output: false
Explanation:
No element in this array is double another element, so the answer is false.

Note:
Special attention is required for the value 0 because if there are at least two zeros in the array, then 0 is considered double of 0.

Use a Hash Set or Frequency Map:
Since you need to quickly check whether a value (or its half) exists, a hash set (or frequency map) is an excellent choice.
- For each number n, check if 2 * n is already seen.
- Also, if n is even, check if n / 2 is in the set.
  This way, you cover both cases where n might be the double or the half of another number.
Handling Zero:
When n is 0, since (0 = 2 \times 0), ensure that the algorithm correctly identifies that at least two 0s must be present.

Idea:
Traverse through the array while maintaining a hash set (or frequency map) of numbers encountered so far. For every element n, check whether:
- 2 * n exists in the set, or
- If n is even, whether n / 2 exists in the set.
Steps:
1. Initialize an empty set.
2. Iterate over each number n in the array.
3. Check if 2 * n or (if n is even) n / 2 is in the set.
4. If found, return true immediately.
5. Otherwise, add n to the set.
6. If no valid pair is found after processing all elements, return false.
Handling Special Case (0):
When processing 0, the check ensures that if another 0 is found later (or if 0 is already in the set), the function returns true.

Idea:
First, sort the array. Then, for each element, perform a binary search for its double.
Steps:
1. Sort the array.
2. For each element n in the sorted array, perform a binary search to look for 2 * n.
3. Return true if found (ensuring that the indices are different).
4. If no such pair exists, return false.
Note:
This approach runs in $(O(n \log n))$ due to the sort and binary search steps and is slightly less efficient than the hash set approach for this problem.

Below is the Python implementation using the hash set approach:

Python3

. . . .

Java

. . . .

Consider the array [10, 2, 5, 3]:

Initialization:
- Start with an empty set: seen = {}.
Iteration:
- First Element:
  - num = 10
  - Check if $(2 \times 10 = 20)$ is in seen → No.
  - 10 is even; check if (10 / 2 = 5) is in seen → No.
  - Add 10 to seen: seen = {10}.
- Second Element:
  - num = 2
  - Check if $(2 \times 2 = 4)$ is in seen → No.
  - 2 is even; check if (2 / 2 = 1) is in seen → No.
  - Add 2 to seen: seen = {10, 2}.
- Third Element:
  - num = 5
  - Check if $(2 \times 5 = 10)$ is in seen → Yes (10 is in seen).
  - Since a valid pair is found (5 and 10), the function returns true.
Conclusion:
The method returns true because 10 (which is already in the set) is double 5.

Ignoring the Case When n is 0:
Since $(0 = 2 \times 0)$ , failing to correctly handle duplicate zeros may result in an incorrect answer.
Not Checking Both Directions:
Ensure you check both whether the current number’s double exists and, if applicable, whether its half exists.
Using Inefficient Brute Force Methods:
A double loop that checks every pair leads to an $(O(n^2))$ time complexity, which is unnecessary for the problem size.

Single Element Array:
The array must have at least two elements for a valid pair. An array with a single element should return false.
Multiple Zeros:
An array with two or more zeros should return true.
Negative Numbers:
The same logic applies for negative numbers since the doubling relationship holds regardless of sign.

Variations:
- Check if there exists a pair such that one number is a multiple (other than double) of the other.
- Modify the problem to look for a pair with a fixed multiplication factor.
Related Problems for Further Practice:
- "Two Sum" – finding a pair of numbers that add up to a target.
- "Find Pair With Given Sum" – similar pairing problems.
- "Contains Duplicate" – using hash sets to detect repeated elements.

Hash Set Approach:
- Time Complexity: (O(n)) since each element is processed once.
- Space Complexity: (O(n)) for storing the elements in the hash set.
Sorting and Binary Search Approach:
- Time Complexity: $(O(n \log n))$ due to sorting and binary search steps.
- Space Complexity: (O(1)) or (O(n)) depending on the sorting algorithm used.