check if there exists a[i] = 2*a[j] in an unsorted array a?

Question

Given a unsorted sequence of a[1,...,n] of integers, give an O(nlogn) runtime algorithm to check there are two indices i and j such that a[i] =2*a[j]. The algorithm should return i=0 and j=2 on input 4,12,8,10 and false on input 4,3,1,11.

I think we have to sort the array anyways which is O(nlogn). I'm not sure what to do after that.

Answer 1

Note: that can be done on O(n)¹ on average, using a hash table.

set <- new hash set
for each x in array:
   set.add(2*x)
for each x in array:
   if set.contains(x): 
        return true
return false

Proof:
=>
If there are 2 elements a[i] and a[j] such that a[i] = 2 * a[j], then when iterating first time, we inserted 2*a[j] to the set when we read a[j]. On the second iteration, we find that a[i] == 2* a[j] is in set, and return true.

<=
If the algorithm returned true, then it found a[i] such that a[i] is already in the set in second iteration. So, during first itetation - we inserted a[i]. That only can be done if there is a second element a[j] such that a[i] == 2 * a[j], and we inserted a[i] when reading a[j].

Note:
In order to return the indices of the elemets, one can simply use a hash-map instead of a set, and for each i store 2*a[i] as key and i as value.

Example:
Input = [4,12,8,10]

first insert for each x - 2x to the hash table, and the index. You will get:

hashTable = {(8,0),(24,1),(16,2),(20,3)}

Now, on secod iteration you check for each element if it is in the table:

arr[0]: 4 is not in the table
arr[1]: 12 is not in the table
arr[2]: 8 is in the table - return the current index [2] and the value of 8 in the map, which is 0.

so, final output is 2,0 - as expected.

---

(1) Complexity notice:
In here, O(n) assumes O(1) hash function. This is not always true. If we do assume O(1) hash function, we can also assume sorting with radix-sort is O(n), and using a post-processing of O(n) [similar to the one suggested by @SteveJessop in his answer], we can also achieve O(n) with sorting-based algorithm.

Answer 2

1. Sort the array (O(n log n), or O(n) if you're willing to stretch a point about arrays of fixed-size integers)
2. Initialise two pointers ("fast" and "slow") at the start of the array (O(1))
3. Repeatedly:
   1. increment "fast" until you find an even value >= twice the value at "slow"
   2. if the value at "fast" is exactly twice the value at "slow", return true
   3. increment "slow" until you find a value >= half the value at fast
   4. if the value at "slow" is exactly half the value at "fast", return true
4. if one of the attempts to increment goes past the end, return false

Since each of fast and slow can be incremented at most n times total before reaching the end of the array, the "repeatedly" part is O(n).

Answer 3

You're right that the first step is sorting the array.

Once the array is sorted, you can find out whether a given element is inside the array in O(log n) time. So if for every of the n elements, you check for the inclusion of another element in O(log n) time, you end up with a runtime of O(n log n).

Does that help you?