For given array X[1..m] and Y[1..n] , find number of pairs such that x^y > y^x

Reference: http://www.geeksforgeeks.org/find-number-pairs-xy-yx/

Solution: a) Brute force O(m*n)
b) if y > x then x^y > y ^ x (with some exceptions which should not be counted) (rule a)
    if y <= x then x^y <= y^x (with some exceptions which should be counted) (rule b)

To find exceptions, try different values of x
Case x = 0: {Nothing should be counted}
    clearly for no value of y, 0 (0^y) will be greater then 1 (y^0), hence if x = 0 no such pair exist.
Case x = 1: {0s in y should be counted}
    Case y = 0: Exception of rule b
    Case y = 1: fine.
    Case y>1 : Exceptions of rule a
Case x = 2:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y = 2: fine
    Case y = 3: exception of rule a
    Case y = 4: exception of rule a
    Case y > 4: fine
Case x = 3:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y = 2: Exception of rule b
    Case y = 3: fine
    Case y >= 4: fine
Case x > 4:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y > x: fine

Thus sort Y and count number of 0s,1s,2s,3s,4s O(mlogm + m) let it be y0,y1,y2,y3,y4
count = 0
for each X:
  if(x ==0){
  } else if(x==1) {
     count += y0;
  } else if (x==2) {
     count += y0 + y1;
     //binary search in y to fine least value greater than x, let it be i
      count += (n-i - y3-y4);
  } else if (x==3) {
     count += y0 + y1 + y2;
     //binary search in y to fine least value greater than x, let it be i
     count += (n-i);
  } else {
      count += y0 + y1;
       //binary search in y to fine least value greater than x, let it be i
       count += (n-i);
  }