Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b < 1$.

For example:

  • Input: $2, 3, 1, 0.5, 3, 1.6$.
  • Output: $(2,3), (3,2), (3,3), (3,1.6), (1.6,3)$.

    We can compare each element with each other but it takes $O(n^2)$ complexity. How to improve that algorithm? Maybe use special structure? Maybe use sorting?

  • $\begingroup$ I think if we have additional information about the numbers in the array, then we can do better than $O(n^2)$. For example, if the numbers are positive and greater than $2$, then sorting helps to identify all pairs because: if $2<a<b$, then $a+b<ab$. If the numbers are positive only, maybe you can split them into two groups; the ones which are greater than $2$ and the others. $\endgroup$ – zdm87 Aug 26 '18 at 15:38

Assume that $a$ is given. Then a valid $b$ has to satisfy (just rearrange the inequality) :

$$b > \frac{a}{a - 1}$$

Notice, if the array is sorted, then you can find the number of valid $b$ using binary search, which gives $O(n \log n)$ to compute the number of all pairs.

Also notice, that if $a$ gets bigger, then $b$ is allowed to be smaller. So if you you iterate over $a$ in sorted order, and keep a pointer (to indicate the allowed elements for $b$), you don't need to use binary search and can compute the result in $O(n)$.

  • $\begingroup$ github.com/ArtemMe/java-interview/blob/test/src/main/java/bets/… I wrote a code on this algorithm, look at that)) $\endgroup$ – Артем Межеловский Aug 28 '18 at 9:22
  • $\begingroup$ @АртемМежеловский I looked. Do you want me do something else too? :-P $\endgroup$ – Jakube Aug 28 '18 at 10:49
  • $\begingroup$ I don't see how this code reassembles what I said in the post. For every possible value $a$, you can compute a lower bound for $b$, and therefore (by binary search) you can count how many such pairs are there for each $a$. $\endgroup$ – Jakube Aug 28 '18 at 10:51
  • $\begingroup$ The second, faster version, just replaces the binary search with a pointer, that initially points after the last element (since no pair might be valid), and gets smaller and smaller as $a$ increases. $\endgroup$ – Jakube Aug 28 '18 at 10:53
  • $\begingroup$ Also: I hope you only plan on printing the pairs for testing purposes. Because printing all pairs requires $O(n^2)$ in the worst case. $\endgroup$ – Jakube Aug 28 '18 at 10:54

Assuming the numbers are integers >= 1, the sum of two reciprocals is less than 1 unless one integer is 1, or both integers are two.

So assuming you have X array elements > 2, Y array elements = 2, and Z array elements = 1, your solution will contain (X+Y) (X+Y+1)/2 - Y(Y+1)/2 = X(X+1)/2 + XY pairs of numbers.

If you represent the solution as pairs of numbers, then the time is at least as large as the size of the solution, which will be quadratic unless Z is very large.

It's in the nature of the problem that the solution is HUGE and therefore it takes a long time to produce the solution.

If your numbers are reals, you throw away anything >= 1, split into number <= 2 and numbers > 2. All pairs of numbers > 2 are solutions, the number of these pairs can be quadratic. Pairs of numbers <= 2 are not solutions. What remains are pairs of one number <= 2 and one number > 2. Sort the smaller set, then for each member x of the larger set use binary search to find all elements y of the other set with y > x / (x - 1). This works especially well if one set is small.

Of course you can avoid all the difficulties with reciprocals if you just replace each number x with 1/x.


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.