## Given problem

Given an array arr of integers, check if there exists two integers `N` and `M` such that `N` is the double of `M` ( i.e. `N = 2 * M`).

More formally check if there exists 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: N = 10 is the double of M = 5,that is, 10 = 2 * 5.
Example 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.
Example 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.
``````

Constraints:

• `2 <= arr.length <= 500`
• `-10^3 <= arr[i] <= 10^3`

## Using Brute-force solution

According to the requirements above, we can see that we need to find the two elements `N` and `M`. Then, we can use brute-force algorithm with two loops to iterate all elements in that array.

``````public static boolean checkIfExist(int[] arr) {
int length = arr.length;

for (int i = 0; i < length; ++i) {
for (int j = 0; j < length; ++j) {
if (i != j) {
if (arr[i] == 2 * arr[j]) {
return true;
}
}
}
}

return false;
}
``````

The complexity of this solution:

• Time complexity: O(n^2)
• Space complexity: O(1)

## Using Binary Search algorithm

To solve this problem, we will need to sort this array firstly. Then, we will use Binary Search algorithm to search each element in this array.

``````class Solution {
public boolean checkIfExist(int[] arr) {
if (arr == null || arr.length < 2) {
return false;
}

Arrays.sort(arr);

for (int i = 0; i < arr.length; ++i) {
int currentValue = arr[i];
int idx = Arrays.binarySearch(arr, 2 * currentValue);
if (idx >= 0 && idx != i) {
return true;
}
}

return false;
}
}
``````

In this solution, we will use `Arrays.binarySearch()` method to search it.

• If an element is existed in the array, this method will return the index of this element.
• Otherwise, it will return `(-(insertion point) - 1)`. The insertion point is defined as the point at which the key would be inserted into the array.

Note that this guarantees that the return value will be >= 0 if and only if the key is found.

The complexity of this solution:

• Time complexity: O(nlogn)
• Space complexity: O(1)

## Using other solutions

If we look carefully at this problem, we can see this problem is the same as the Two Sum problem. Then, below is a solution that using HashSet data structure.

``````public boolean checkIfExist(int[] arr) {
Arrays.sort(arr);
Set<Integer> data = new HashSet<>();

for (int i = 0; i < arr.length; ++i) {
int currentValue = arr[i];

if (i > 0 && currentValue != 0 && currentValue == arr[i - 1]) {
continue;
}

if (data.contains(2 * currentValue) || data.contains(currentValue)) {
return true;
}

}

return false;
}
``````

The complexity of this solution:

• Time complexity: O(nlogn)
• Space complexity: O(n)

## Wrapping up

Refer:

1346. Check If N and Its Double Exist

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int)