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