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

Question

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 such 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.

Answer 1

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

Answer 2

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))

Answer 3

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;
}