Geek Answers Handbook

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

Let A be an array of n natural numbers and k be a given integer.

I'm looking for an algorithm to find if there are a couple of elements in the array, so that A[i] * A[j] == kand A[i] == A[j] + k. If there is such a pair, the algorithm should return its index.

This is homework, and we are told that there is a solution O (n * log (n)).

+5
source share
5 answers

Here is a few clarified Graphics Noob solution.

Also, this is more like O (N) (assuming that hashing won't let us down) rather than 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;
}
+2
source 
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))
+3
source

, :

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

, O (n) O (log n), ( TreeMap, HashMap , )

: , ),

+3

nlog (n)

, A [j] , . ,

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

+2

k , x, y , x * y = k. (x, y), , A [i] = x [i] = y. = O (n) * # k = O (n) (, )

The problem states that A [i] is all positive, so k can also be decomposed x + y = k in the end, so O (n) as well.

0
source

More articles:


All Articles