# How do you solve this [1,5,9,4] pair numbers problem?

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

• 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$)? – greybeard Oct 22 '18 at 19:34

This can be done in $O(n^2 \space log \space n)$.
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)$.