# Check If N and Its Double Exist
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-n-and-its-double-exist)
Canonical: https://scaleengineer.com/dsa/problems/check-if-n-and-its-double-exist
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
Given an array `arr` of integers, check if there exist two indices `i` and `j` such that :

* `i != j`
* `0 <= i, j < arr.length`
* `arr[i] == 2 * arr[j]`

**Example 1:**

**Input:** arr = [10,2,5,3]
**Output:** true
**Explanation:** For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

**Example 2:**

**Input:** arr = [3,1,7,11]
**Output:** false
**Explanation:** There is no i and j that satisfy the conditions.

**Constraints:**

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

# Approaches
## Brute Force using Nested Loops
The most straightforward approach is to check every possible pair of elements in the array. We can use two nested loops to iterate through all pairs of indices `(i, j)` and verify if the condition `arr[i] == 2 * arr[j]` holds, ensuring that `i` and `j` are not the same.
**Time:** O(N^2), where N is the number of elements in the array. For each element, we iterate through the entire array again, leading to a quadratic number of comparisons. · **Space:** O(1), as we only use a few variables to store indices and the array length, which does not depend on the input size.
**Pros:** Simple to understand and implement.; Requires no extra memory, making it space-efficient.
**Cons:** Highly inefficient for large arrays due to its quadratic time complexity.; Performs many redundant checks.
### Explanation
This method involves a systematic check of all pairs. The outer loop selects an element `arr[i]`, and the inner loop iterates through all other elements `arr[j]` to see if `arr[j]` is half of `arr[i]`. The algorithm is as follows:

```java
class Solution {
    public boolean checkIfExist(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // The indices must be different
                if (i != j && arr[i] == 2 * arr[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   Initialize two nested loops, with iterators `i` and `j`, both from `0` to `arr.length - 1`.
*   Inside the inner loop, check if the indices are different (`i != j`).
*   If the indices are different, check if the condition `arr[i] == 2 * arr[j]` is met.
*   If the condition is true, a valid pair has been found, so return `true` immediately.
*   If the loops complete without finding any such pair, it means no such pair exists. Return `false`.

## Sorting with Binary Search
A more optimized approach involves sorting the array first. Once the array is sorted, for each element `x`, we can use binary search to efficiently find if its double (`2*x`) exists in the array. This avoids the need for a linear scan for each element.
**Time:** O(N log N). Sorting the array takes O(N log N). The subsequent loop runs N times, with each iteration performing a binary search that takes O(log N). The total time is dominated by the sorting step. · **Space:** O(log N) to O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types has an average space complexity of O(log N) for the recursion stack.
**Pros:** Significantly faster than the brute-force approach for larger arrays.; A good trade-off between time and space complexity.
**Cons:** The in-place sort modifies the original array, which might not be desirable.; More complex to implement correctly, especially handling the `i != j` condition with binary search.
### Explanation
By sorting the array, we can leverage the ordered property to speed up the search. For each element `arr[i]`, we calculate the `target` value (`2 * arr[i]`). Then, we perform a binary search for this `target` in the array. A crucial detail is to ensure that if the `target` is found at an index `j`, it must be a different element, i.e., `j != i`. This is particularly important for the case where `arr[i]` is 0. A robust way to handle this is to define the search space for the binary search to exclude the current index `i`.

```java
import java.util.Arrays;

class Solution {
    public boolean checkIfExist(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            int target = 2 * arr[i];
            // Define the search range to exclude the current element.
            // If target is larger, search to the right. If smaller, search to the left.
            int low, high;
            if (arr[i] >= 0) {
                low = i + 1;
                high = arr.length - 1;
            } else { // arr[i] < 0, so 2 * arr[i] < arr[i]
                low = 0;
                high = i - 1;
            }
            
            // Standard binary search in the defined range
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (arr[mid] == target) {
                    return true;
                } else if (arr[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   First, sort the input array `arr` in non-decreasing order.
*   Iterate through the sorted array with an index `i` from `0` to `arr.length - 1`.
*   For each element `arr[i]`, calculate the `target` value, which is `2 * arr[i]`.
*   Perform a binary search for the `target` in the rest of the array, excluding the element at index `i`.
*   If the binary search finds the `target`, return `true`.
*   If the loop finishes without finding any such pair, return `false`.

## Optimal Approach using a HashSet
The most efficient solution uses a HashSet to achieve linear time complexity. We iterate through the array, and for each element, we check if its double or its half already exists in the set of numbers we've seen so far. This avoids repeated computations and searches.
**Time:** O(N), where N is the number of elements in the array. We iterate through the array once, and each HashSet operation (insertion and lookup) takes O(1) time on average. · **Space:** O(N), as in the worst-case scenario (no duplicates and no valid pairs), the HashSet will store all N elements from the array.
**Pros:** Optimal time complexity of O(N).; The logic is straightforward and handles all cases, including zeros, elegantly.
**Cons:** Requires extra space proportional to the number of elements in the array.
### Explanation
We can use a `HashSet` for O(1) average time complexity lookups. We iterate through the array `arr` once. For each number `num`, we check two conditions before adding it to our set of seen numbers:
1.  Does `2 * num` exist in the set? If so, we've found a number that is half of an existing number.
2.  Is `num` even, and does `num / 2` exist in the set? If so, we've found a number that is double an existing number.
If either of these conditions is true, we return `true`. Otherwise, we add the current number `num` to the set and continue. This ensures we find a pair regardless of the order they appear in the array.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        for (int num : arr) {
            // Check if the double exists or if the half exists
            if (seen.contains(2 * num) || (num % 2 == 0 && seen.contains(num / 2))) {
                return true;
            }
            // Add the current number to the set for future checks
            seen.add(num);
        }
        return false;
    }
}
```
### Algorithm
*   Initialize an empty `HashSet` called `seen` to store the numbers encountered so far.
*   Iterate through each number `num` in the input array `arr`.
*   For each `num`, check if `seen` contains `2 * num`.
*   Also, check if `num` is an even number and if `seen` contains `num / 2`.
*   If either of the above checks is true, it means we have found a valid pair. Return `true`.
*   If not, add the current `num` to the `seen` set.
*   If the loop completes, it means no such pair was found. Return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean checkIfExist(int[] arr) {
    Map<Integer, Integer> m = new HashMap<>();
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      m.put(arr[i], i);
    }
    for (int i = 0; i < n; ++i) {
      if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {
        return true;
      }
    }
    return false;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} arr * @return {boolean} */ var checkIfExist = function (
  arr,
) {
  const s = new Set();
  for (const v of arr) {
    if (s.has(v << 1) || s.has(v / 2)) {
      return true;
    }
    s.add(v);
  }
  return false;
};

```

### CPP

```cpp
class Solution {
public:
  bool checkIfExist(vector<int> &arr) {
    unordered_map<int, int> m;
    int n = arr.size();
    for (int i = 0; i < n; ++i)
      m[arr[i]] = i;
    for (int i = 0; i < n; ++i)
      if (m.count(arr[i] * 2) && m[arr[i] * 2] != i)
        return true;
    return false;
  }
};

```

### Python

```python
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool: m = {v: i for i, v in enumerate(arr)} return any(v << 1 in m and m[v << 1] != i for i, v in enumerate(arr))

```