1
$\begingroup$

So given an array of [1,5,9,4], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs satisfying this condition. (If a pair has 2 math operators that fit to the same number or if a pair can combine to 2 different numbers, dont count it twice).

How do I start this? and how do I explain my asymptotic complexity(Im a noob wit this)?

$\endgroup$
  • $\begingroup$ numbers from which domain? Natural/integral numbers? You may need to specify (the result of) integral division. Is $(5, 4)$ the same pair as $(4, 5)$? I think you can exclude $0$ from add/subtract as well as from divide/multiply, and $1$ from the latter. If a pair has 2 math operators that [result in] the same number can this happen for the operations mentioned ($3/2$ & $3-2$)? $\endgroup$ – greybeard Oct 22 '18 at 19:34
1
$\begingroup$

This can be done in $O(n^2 \space log \space n)$.

  1. Insert all N array elements with the indexes into a balanced BST.
  2. For every $i \in \{0,...N-1\}$
  3. For every $j \in \{0,...N-1\} \space and \space j \ne i$
  4. Search for $(A[i]+A[j]),(A[i]-A[j]),(A[i]*A[j]),(A[i]/A[j])$ in the BST and add $(A[i],A[j])$ if it is found in the BST and its corresponding BST entry $index \ne i\space and \space j$

    Steps 1 and 2 runs for $O(n)$ time.
    Step 2 runs for $n-1$ times = $O(n)$.
    Step 3 runs for $4*log\space n = O(log\space n)$.
    Hence, time complexity is $O(n^2\space log \space n)$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.