A[i] * A[j] = k in O(nlog(n))

Question

A is an Array of n positive int numbers k given int

Algorithm should find if there is a pair of numbers which product gives the result
a. A[i] * A[j] = k
b. A[i] = A[j] + k

if there is such a couple the algorithm should return thier index.

thanks in advance.

Answer 1

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)

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

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 4

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

Answer 5

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.