CODEWITHSUNDEEP
c++arraysalgorithmdata-structures
user12693890
user12693890

Reputation:

Efficient way to find numbers that multiply to given numbers

I'm given 2 lists, a and b. Both them contain only integers. min(a) > 0, max(a) can be upto 1e10 and max(abs(b)) can be upto 1e5. I need to find the number of tuples (x, y, z), where x is in a and y, z are in b such that x = -yz. The number of elements in a and b can be upto 1e5.

My attempt:

I was able to come up with a naive n^2 algorithm. But, since the size can be upto 1e5, I need to come up with a nlogn solution (max) instead. What I did was:

  1. Split b into bp and bn where the first one contains all the positive numbers and second one contains all the negative numbers and created their maps.

  2. Then:

    2.1 I iterate over a to get x's.

    2.2 Iterate over the shorter one of bn and bp. Check if the current element divides x. If yes, use map.find() to see if z = -x/y is present or not.

What could be an efficient way to do this?

Upvotes: 7

Views: 580

Answers (3)

ElKamina
ElKamina

Reputation: 7817

  • Step 1: Sort the elements in list b (say bsorted)
  • Step 2: For a value x in a, go through the list bsorted for every value y in bsorted and binary search for (-x/y) on bsorted to find z

Complexity |a|=m and |b|=n complexity is O(mnlogn)

Upvotes: 1

karpada
karpada

Reputation: 185

There's no O(n*logn) because: z = -x/y <=> log(z) = log(-x) - log(y)

As https://stackoverflow.com/users/12299000/kaya3 has mentioned, it is 3SUM#3_different_arrays. According to wikipedia:

Kane, Lovett, and Moran showed that the 6-linear decision tree complexity of 3SUM is O(n*log^2n)

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23945

Here's an untested idea. Create a trie from the elements of b, where the "characters" are ordered prime numbers. For each element in a, walk all valid paths in the trie (DFS or BFS, where the test is being able to divide further by the current node), and for each leaf reached, check if the remaining element (after dividing at each node) exists in b. (We may need to handle duplicates by storing counts of each "word" and using simple combinatorics.)

Upvotes: 0

Related Questions