algorithm - 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).