CODEWITHSUNDEEP
algorithmmathtime-complexity
gabi
gabi

Reputation: 1376

compute number of pairs in a given array with a specific condition

How can we compute number of pairs (P,Q) in a given array, Q>P, such that C[P] * C[Q] ≥ C[P] + C[Q] with complexity O(N) ?

Upvotes: 0

Views: 951

Answers (3)

esavier
esavier

Reputation: 463

I am not math-brain myself but i see a pattern here. you didn't included it here, but there is assumption that is really helping here.

  • array is sorted in non-decreasing order
  • P
  • if out >= 1 000 000 000 return 1 000 000 000
  • (tip) if pair (x,y) is good, any next pair from this row is good (x, y+1) (x, y+n) you just need to find the first one. Why? look how plots from (x+y) and (x*y) looks like... there is joint point after which every next pair will work.

Look at example: [lets assume natural numbers] like that: 1,2,3,4,5,6,7,8... will give u pairs :

    • pairs are (x,y) -> [ (A[x]*A[y]) >= (A[x]+A[y]) ]
  • none for x == 1 :
    • ( parallel plots a+b and a*b for a=1 and a=0, no matter b),
  • A[y] == 3 or more for A[x] == 2 (y=2 break condition y>x)
  • A[y] == 4 or more for A[x] == 3 etc

here I posted my code, it scored 45% so its not so bad.

I hope someone will catch up my idea and somehow improve this. Good luck :). 

inline double real (std::vector<int> &A, std::vector<int> &B, int i)
{
    return (double)((double)A[i] + ((double)B[i]/1000000));
}

int solution(std::vector<int> &A, std::vector<int> &B)
{
    int size = A.size();
    int pairs = 0;
    if (size < 2) return pairs;

    for(int x = 0; x<size; ++x)
    {
        for(int y = x+1; y<size; ++y)
        {
            double lx = real(A,B,x);
            double ly = real(A,B,y);
            double m = lx*ly;
            double a = lx+ly;
            if(m<a) continue;
            pairs+=(size-y);
            if (pairs >= 1000000000) return 1000000000
            break;
        }
    }
    return pairs;
}

Upvotes: 0

Ron Teller
Ron Teller

Reputation: 1890

I believe this is impossible in the general case (for real numbers), but under some assumptions on the numbers, it is possible.

For example, consider the case of non-negative integers:

Let X and Y be non-negative integers:

  • If X=0 and Y=0: X + Y = X * Y
  • If X=0 or X=1, for any Y>0: X + Y > X * Y
  • If Y=0 or Y=1, for any X>0: X + Y > X * Y
  • In any other case: X + Y <= X * Y

So we can run across the array, and count the number of 0's, 1's, and greater than 1's (this takes O(n) time):

We're only interested in combinations of pairs where both numbers are from the group "greater than 1's", or the group of "0's" (any other combination of numbers doesn't satisfy the condition).

Let's say the number of pairs in the first group is n and the second group is m, the total number of pairs satisfying the condition X * Y >= X + Y is:

n(n-1)/2 + m(m-1)/2 (representing the number of possible pairs in each group).

This method can probably be extended to other classes of numbers (e.g. signed integers).

Upvotes: 1

Tim B
Tim B

Reputation: 41188

You can't do this as a straightforward programming approach with O(N) complexity as you have N^2 combinations to try.

Just do nested for loops performing the comparison and computer the results.

i.e.

int count = 0;
for (int i=0;i<len;i++) {
   for (int j=i+1;j<len;j++) {
      if (arr[i]*arr[j] >= arr[i]+arr[j]) {
         count++;
      }
   }
}

Note that I loop from i in the inner loop so each pair only gets scanned once.

It sounds like there is some "trick" algorithm involved that will allow you to get linear but that's a math/algorithms problem not a programming one and I don't see anything obvious.

Upvotes: 0

Related Questions