I was thinking about the homework problem:Given $n$ vectors in 3D: $(\mathbf{v_1},\mathbf{v_2},\dots, \mathbf{v_n})$. Their coordinates are positive integers and less than $10^9$.  We should split this set into $k$ groups in the way that each two  vectors from one group are collinear and from different are not.So, for example, the set $\big((2,2,2), (3,3,3), (4,5,4), (8,10,8)\big)$ should be split into 2 groups.If we divide coordinates of each vector $\mathbf{v}$ by $\text{gcd}(x_{\mathbf{v}}, y_{\mathbf{v}}, z_{\mathbf{v}})$. then in each group vectors should be mutually equal and vice versa. So, the problem is to find the number of unique vectors in the set.I need to develop an algorithm to calculate k efficiently.1. I need an algorithm of $O(n)$ expected running time. I know that we could build this groups by sorting, but unfortunately I banned with sorting for this problem.2. I suppose that we could build something with hashing and disjoint-set data structure. The draft of the solution in this case is following:Considering only x-coordinate we hash vectors into $m_x$ buckets by a hash-function taken from a universal set.Each bucket we hash again considering y-coordinate. And again for z-coordinate.For each received bucket we launch an $O(n^2)$ pairwise algorithm and form groups. There we willl need disjoint-set data structure to maintain formed groups. This solution is simple but requires quite a lot memory. Are there any approaches to solve the problem?
Find unique vectors by linear algorithm
algorithms;data structures;hash tables