How to find pairs with product greater than sum

Question

Supposing that we have a array C with all element in C > 0

A pair of indices (a, b) is multiplicative if 0 ≤ a < b < N and C[a] * C[b] ≥ C[a] + C[b]. with the time-complexity is O ( n )

• expected worst-case time complexity is O(N);

I appreciate your help in supporting this case. Thanks.

Answer 1

The O(N) solution is here.

It is supposed that elements in the array are sorted in non-decreasing order. If the array is not sorted, then worst-time complexity O(N) is unreacheble.

The original condition C[a] * C[b] ≥ C[a] + C[b] can easily be expressed as C[b] ≥ C[a] / (C[a] - 1)

So, Looking at the graph of C[a] / (C[a] - 1) ...

...we can see that:

1. If 0 ≤ C[a] < 1, then (a, b) is multiplicative only if C[a] = 0
2. If 1 < C[a] < 2, then C[a] / (C[a] - 1) > 2, therefore C[b] > 2. So, C[b] > C[a], but this is impossible because C[a] ≥ C[b] (because the array is sorted).
3. If C[a] > 2 then the pair is multiplicative for any C[b] where C[b] ≥ C[a] / (C[a] - 1)

So, the code in C# may look like:

int count_pairs(double[] C)
{
  int result = 0;
  int len = C.Length;

  if (len > 1)
  {
    int lo_index;
    int hi_index = len - 1;

    // Skip all C[i] less than 1
    for (lo_index = 0; lo_index < len; lo_index++)
    {
      if (C[lo_index] > 1)
        break;
    }

    while (hi_index > lo_index)
    {
      double v = C[hi_index] / (C[hi_index] - 1);

      while (lo_index < hi_index && C[lo_index] < v)
      {
        lo_index++;
      }

      if (lo_index == hi_index)
        break;

      result += (hi_index - lo_index);

      hi_index--;

    }
  }
  return result;  
}

Answer 2

As always with competition problems, you have to solve the problem before you code it. In this case you'll need some basic algebra. I'll ignore the strange formatting of numbers and operate only on C.

So, given a non-negative number a, what non-negative number b would yield a * b >= a + b?
a * b >= a + b => b * (a-1) >= a
Now, we have 4 cases:

1. 0 < a < 1. In this case the next step is b <= a / (a-1). Note that the RHS is negative, while b is non-negative. Hence there are no such b
2. a == 0. Next step is -b >= 0, hence, since b is non-negative, b == 0
3. a == 1. Next step is b * 0 >= 1 which simplifies to false. Hence, there are no such b
4. 1 < a. Next step is b >= a / (a-1). This is the only non-trivial case.

This, in itself, already gives you an O(N* log(N)) algorithm:
Iterate through the array keeping the sum. For each number, if it is 0, find the number of 0s in the array and add them to the sum. If it is 0 < num <= 1, add 0. If it is > 1, add the number of values >= num / (num-1). Since the array is ascending you can use binary search to find those values in log(N) time, giving you a total N * log(N) worstcase runtime (And O(N) best runtime, in case all values are the noops - between 0 and 1)

To make the last step to optimize the algorithm even further to O(N) you need to observe how the function x / (x-1) behaves when x > 1 and x is growing (i.e. what will your search target be as you iterate through the array).