*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]

I have solved this question using nested loops and T/C for the approach is obviously O(n^2). But I have seen the solutions using hashmap or set in Javascript which essentially brings the T/C to O(n). But, I am not getting the intuition behind using a set in this question. How is it relevant? If anyone could explain this, please. Thanks.

·
Juan Pablo Isaza

You could convert your array to an object or set. Loop through the array, check if element * 2 is in the object/set.

```
const arr = [1,3,5,7,9,11,14];
const obj = Object.fromEntries(arr.map(el => [el, true])); // O(n)
// obj looks like
//{ "1": true, "3": true, etc}
// loop through arr until we find an element such that twice the element is in obj. Can use O(1) lookups in obj
const result = arr.some(el => obj[el * 2]); // O(n) (usually less)
console.log(result);
```

·
Juan Pablo Isaza
Report