Find how many different float values I have in an array

Question

In order to solve a section from a problem, in which I'm given n pairs of integers x and y, I need to find how many different x/y are there. (the precise value, with decimals)

1.

Of course I could just iterate through all the previous pairs and see if the same x/y value occurred before, but that would take, I believe, (n^2)/2 time.

I tried using a hash table, the it doesn't seem to function very well with float values. Maybe it would work with a very good hash function.

2.

Considering that x and y are integers, I tried a different approach to the problem:

• Compute the greatest common divisor for each pair
• Divide x and y with the GCD

• Use a matrix m[max_value_of_x][max_value_of_y] and do this:

  if ( m[x][y] ) { ; } else { m[x][y] = 1 ; cnt++ ; } 
  

• After doing this for all the pairs, the cnt should be number of different float values.

Although this could run, I think, in a decent amount of time; it is definitively not space efficient. In the problem actually, the max value for x and y is 1000, but the memory allocated is quite low.

Answer 1

From MBo 's solution using a set :

struct cmp_div {
    bool operator ()(const std::pair<int, int>& xy1, const std::pair<int, int>& xy2) const {
        // x1/y1 < x2/y2
        return xy1.first*xy2.second < xy2.first*xy1.second;
    }
};

std::set<std::pair<int, int>, cmp_div> c;
c.emplace(6, 2);
c.emplace(9, 3);
std::cout << c.size(); // == 1

Answer 2

You can store x/y pairs in list or array, and sort this list with comparator function, which compares x1*y2 and x2*y1 - note that all calculations are in integers. After sorting (NlogN), walk the list and count different values (comparing neighbours only)

Answer 3

Another approach can be storing all the x/y values in a set and avoid duplicate entries. This can be achieved by

      set < float > store ; // choose the datatype according to the precison needed .
      // If arr[] is the given array containing pair x and y .
      store . clear () ; .
      for ( i = 0 ; i < arr.size() ; i++)
       {  x = arr[i].first ; y = arr[i].second ;
          float y = (x/gcd(x,y) / (y/gcd(x,y)) ; // For precison round the values   
           store.insert ( y ) ;
        }