Finding pairs of numbers in array whose reciprocals sum to 1 Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b &lt; 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?
Assume that $a$ is given. Then a valid $b$ has to satisfy (just rearrange the inequality) :

$$b &gt; \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)$.