Check if [i] = 2 * a [j] exists in unsorted array a?

Question

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

I think we should sort the array anyway, like O (nlogn). I'm not sure what to do after this.

Answer 1

You are right that the first step is to sort the array.

After sorting the array, you can find out if the given element is inside the array at O(log n) time. Therefore, if for each element n you check the inclusion of another element in O(log n) time, you get the runtime O(n log n) .

Does this help you?

Answer 2

Note: what can be done in 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 

Evidence:
=>
If there are 2 elements a[i] and a[j] such that a[i] = 2 * a[j] , then at the first iteration we insert 2*a[j] into the set when we read a[j] . In the second iteration, we find that a[i] == 2* a[j] is in the set and returns true.

<=
If the algorithm returned true, then he found a[i] in such a way that a[i] already in the set at the second iteration. So, during the first iteration, we inserted a[i] . This can be done only 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:
To return element indices, you can simply use a hash map instead of a set, and for each i save 2*a[i] as a key and i as a value.

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

first insert for each x - 2x hash table and index. You'll get:

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

Now, in the iteration of secod, you check 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. 

therefore, the final result is 2.0 - as expected.

---

(1) Notification of difficulty:
Here O(n) takes an O(1) hash function. This is not always true. If we accept the hash function O(1) , we can also assume that sorting using radix-sort is O(n) , and using post-processing O(n) [similar to the one suggested by @SteveJessop in his answer ], we can also achieve O(n) using a sorting algorithm.

Answer 3

• Sort an array ( O(n log n) or O(n) if you want to stretch a point in arrays of integers of a fixed size)
• Initialize two pointers ("fast" and "slow") at the beginning of the array ( O(1) )
• Repeatedly:
  • increment "fast" until you find an even value> = twice the value on "slow"
  • if fast is two times slow, return true
  • The increment is "slow" until you find the value> = half the value in fast
  • if "slow" is half the value of "fast", return true
• If one of the increment attempts goes past the end, return false

Since each of fast and slow can be increased no more than n times more than before the end of the array, O(n) will be "repeatedly".

Answer 4

• Create an array of pairs A = {(a [0], 0), (a [1], 1), ..., (a [n-1], n-1)}
• Sort A,
• For each (a [i], i) in, do a binary search to see if there is a pair (a [i] * 2, j) or not. We can do this because A is sorted.

Step 1 is O (n), and steps 2 and 3 are O (n * log n).

Alternatively, you can do step 3 in O (n) (no binary search needed). Since, if the corresponding element for A [i] is in [j], then the corresponding element for A [i + 1] cannot be in [0..j-1]. So we can save two pointers and find the answer in O (n). But in any case, the whole algorithm will be O (n log n), because we are still sorting.

Answer 5

Sorting an array is a good option - O (nlogn) if you don't have any sort of bucket sort options.

After sorting it, you only need to go through the array twice - I believe this is O (n)

Create a list of "doubles" that starts empty.

Then for each element of the array:

• check item for first item in doubles list
  • If it's the same, you win
  • if the item is higher, align the first item in the doubles list and check again

• add it twice to the end of the "doubleles" list

• keep going until you find a double or reach the end of your first list.

Answer 6

You can also use a balanced tree, but it uses extra space, but also does not harm the array.

Starting with i=0 and increasing i , insert the elements, checking that the tree already has two or two values ​​of the current element.

One of the advantages is that it will work in O(M log M) time, when M = min [max{i,j}] . You could change your sorting algorithm to try to execute O(M log M) , but this can get complicated.

Btw, if you use only comparisons, there is a lower bound on Omega(n log n) , reducing the problem of distinguishing an element to this:

Duplicate the input array. Use the algorithm for this problem twice. Therefore, if you do not introduce material such as hashing into the image, you cannot get an algorithm better than Theta(n log n) !