Finding pairs with product greater than sum

Question

Given as input, a sorted array of floats, I need to find the total number of pairs (i,j) such as A[i]*A[j]>=A[i]+A[j] for each i < j. I already know the naive solution, using a loop inside other loop, which will give me O(n^2) algorithm, but i was wondering if there is a more optimal solution.

Answer 1

Here's an O(n) algorithm.

Let's look at A * B >= A + B.

• When A, B <= 0, it's always true.

• When A, B >= 2, it's always true.

• When A >= 1, B <= 1 (or B >= 1, A <= 1), it's always false.

• When 0 < A < 1, B < 0 (or 0 < B < 1, A < 0), it can be either true or false.

• When 1 < A < 2, B > 0 (or 1 < B < 2, A > 0), it can be either true or false.

Here's a visualization, courtesy of Wolfram Alpha and Geobits:

Now, onto the algorithm.

* To find the pairs where one number is between 0 and 1 or 1 and 2 I do something similar to what is done for the 3SUM problem.

* "Pick 2" here is referring to combinations.

• Count all the pairs where both are negative

  Do a binary search to find the index of the first positive (> 0) number - O(log n).

  Since we have the index, we know how many numbers are negative / zero, we simply need to pick 2 of them, so that's amountNonPositive * (amountNonPositive-1) / 2 - O(1).

• Find all the pairs where one is between 0 and 1

  Do a binary search to find the index of the last number < 1 - O(log n).

  Start from that index as the right index and the left-most element as the left index.

  Repeat this until the right index <= 0: (runs in O(n))

  • While the product is smaller than the sum, decrease the left index

  • Count all the elements greater than the left index

  • Decrease the right index

• Find all the pairs where one is between 1 and 2

  Do a binary search to find the index of the first number > 1 - O(log n).

  Start from that index as the left index and the right-most element as the right index.

  Repeat this until the left index >= 2: (runs in O(n))

  • While the product is greater than the sum, decrease the right index

  • Count all the elements greater than the right index

  • Increase the left index

• Count all the pairs with both numbers >= 2

  At the end of the last step, we're at the first index >= 2.

  Now, from there, we just need to pick 2 of all the remaining numbers,
  so it's again amountGreaterEqual2 * (amountGreaterEqual2-1) / 2 - O(1).

Answer 2

You can find and print the pairs (in a shorthand form) in O(n log n).

For each A[i] there is a minimum number k that satisfies the condition(1). All values greater than k will also satisfy the condition.

Finding the lowest j such that A[j] >= k using binary search is O(log n).

So you can find and print the result like this:

(i, j)
(1, no match)
(2, no match)
(3, >=25)
(4, >=20)
(5, >=12)
(6, >6)
(7, >7)
...
(n-1, n)       

If you want to print all combinations, then it is O(n^2), because the number of combinations are O(n^2).

(*) To handle negative numbers it actually needs to be a bit more complex, because the numbers that satify the equation can be more that one range. I'm not absolutely sure how it behaves for small negative numbers, but if the number of ranges is not absolutely limited then my solution is no longer better than O(n^2).