patternMinor
Finding pairs of numbers in array whose reciprocals sum to 1
Viewed 0 times
sumwhosearraynumbersreciprocalsfindingpairs
Problem
Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b
-
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?
-
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?
Solution
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)$.
$$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)$.
Context
StackExchange Computer Science Q#96642, answer score: 3
Revisions (0)
No revisions yet.