Algorithms and Data Structures

Number of Unique Arrays

Given n arrays each one having a length l (l integers), you are asked to calculate the number of unique arrays. The arrays are considered unique if they differ in at least one element.
Notice that comparing arrays one by one might take too long. You can hash an array with some hash function of your choice and try to compare the hashed values.
After that, you can take a large array of size m and fill it with zeros. Every time you obtain a hash, you can mark that location in the array with one. In the end, you can compute the number of ones in the array.
Note that the hash function should be taken modulo m so that the indices take the range [0; m).


The first line of the input contains two integers n (1 ≤ n ≤ 1000) and l (1 ≤ l ≤ 1000).
The next n lines contain l space-separated integers (0 ≤ ).


The program should print the number of unique arrays.


4 3 1 2 3 3 2 1 2 5 3 3 2 1
2 3 1 2 3 4 1 2 3 4
If the hash function is not good enough and there are still collisions, try comparing it with 2 different hash functions - this makes the algorithm twice more robust to collisions.


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue