You are given N numbers in range 1 and 10^18. You should count the number pairs, which have at least one digit in common in their decimal notation and the position of the digits doesn't matter.
example input:
8 (N)
13 51 35 43
output:
5 (13,51),(51,35),(35,43),(51,35),(35,43)
The problem can be solved easily with a complexity of (2^10)*(2^10)(there are at most 10 different digits in a number). We have an array of size 2^10. We find the digits that a number contains for every number. Then we put the numbers, who contain the same set of digits in the same bucket. If a number contains digit 0 it is put in the bucket whose least significant bit is set, for digit 1, the buckets second least significant bit should be etc. After this, you can loop over the buckets like this:
for(int i=0;i<1<<N;i++)
for(int j=0;j<1<<N;j++)
if(i&j) //we should actually add a special case when i equals to j but anyway.
ans+=bucket[i]*bucket[j];
But my question is that could we do this in a better complexity?
I got an idea but I cant compute the bucket version it uses faster than 2^20. Here it is: If we could convert the array we computed above into this:
If a number contains digit 1, it should be put in every bucket whose bit for digit 1 is set. The same thing also applies to the other digits. Then we could compute the number of pairs with the inclusion&exclusion principle. We would just have a 2^N loop and if it has an odd number of set bits, we add it to the answer, if it doesnt, we subtract it from the answer. Actually I got an idea to compute the new array but it doesnt quite work. Some numbers get counted more than once. To fix it I have to use inclusion exclusion principle again. But then the complexity increases to 2^20 again. The wrong version follows:
for(int i=(1<<N)-1;i;i--)
for(int j=i;j;j&=j-1)
bucket[(j&-j)^i]+=bucket[i];
Could you please find a better way to solve this problem?
Thanks in advance.