Find a pair of array elements with a given sum and product in O(n*log(n))

Let A be an array of n positive integers, and k a given integer.

I'm looking for algorithm to find if there is a pair of elements in the array such that A[i] * A[j] == k and A[i] == A[j] + k. If there is s开发者_运维技巧uch a pair, the algorithm should return their index.

This is a homework exercise, and we're told that there is an O(n*log(n)) solution.

First thing off the top of my head:

Make a Map<Integer, Integer>

for each number a in A:
   if (k / a) is a key in the HashMap:
      output the index of a, and HashMap.get(k/a)
   else
      HashMap.add(a, indexof(a))

So it's O(n) to traverse the array, and O(log n) to look up the key in the Map (assuming you used a TreeMap, a HashMap could be better in the best case but worse in the worst case)

Edit: I guess that only answers a) but you get the idea

Sort the array. Also build a permuted index array by initializing an auxiliary array to 0, 1, 2 ... n and swapping indices every time you swap elements in the array, Time O(nLog(n))

for each element a[i] in array, Time O(n)

  Binary Search for (a) k / a[i] or (b) a[i] - k, if found, return index j from permuted index array, Time O(log(n))

Here is somewhat clarified Graphics Noob's solution.

Also, it is more like O(N) (assuming hashing won't fail us), not O(N*log(N)).

Result findMultiplicationIndices(int[] A, int[] B, int k)
{
    HashMap<Integer,Integer> aDivisors = new HashMap<Integer,Integer>();
    for(int i=0;i<A.length;i++)
    {
        int a = A[i];
        if(a!=0)
        {
            int d = k/a;
            if(d*a == k) 
                aDivisors.put(d, i);
        }
    }
    for(int i=0;i<B.length;i++)
    {
        Integer ai = aDivisors.get(B[i]);
        if(ai != null)
            return new Result(ai, i);
    }
    return null;
}

use nlog(n) to sort
then itterate through the array
for each index i calculate what A[j] would need to be in order for the equation to be satisfied
check to see if theres such a value in the array

O(nlogn) + O(N)*O(logn)
=O(nlogn)

If k is fixed, then there are finitely many integers x, y such that x*y = k. For each factor (x,y), iterate through the list finding whether A[i] = x or A[i] = y. Total run time = O(n) * # factors of k = O(n) (deterministically, not assumptions about hashing)

The problem states that A[i] are all positive, so k can be decomposed x + y = k in finitely many ways as well, so O(n) as well.