Check Equality of Two Number Sets

Say we have two lists of numbers. The lists are equal in length but order of elements are not the same. How to find out if the two lists contain the same set of elements?

Intuitive solution is first sort, then compare one by one. Sorting will take O(nlog(n)) time, and can be in place.

Another solution is to use a hashtable. Put every element of the first set on hashtable, and check if every element of the second set is in it. This is O(n) time, but O(n) space.

Is there an solution that is O(n) in time and O(1) in space?

The solution is given by the information theory. This is a mathematically proved solution. Basic idea is to calculate the entropy of the two sets to see if they are equal. I got this solution from heyes.

bool check_set_equality(int array1[], int array2[]) {
  int sum1 := sum of array1 elements;
  int sum2 := sum of array2 elements;
  int min1 := array1 min element;
  int min2 := array2 min element; 
  int N := array length;

  if (sum1 != sum2 || min1 != min2) return false;

  // normalization, result is the same for array2.
  norm = (sum1 - N * min1) / N; 

  double s1 = 0.0, s2 = 0.0, p1, p2;

  for (i = 0; i < N; i ++) {
    p1 = (array1[i] - min1) / norm;
    s1 += p1 * log(p1);
    p2 = (array2[i] - min2) / norm;
    s2 += p2 * log(p2);
  }

  if (s1 == s2) return true;
  else return false;
}