You are given n numbers and you have to find the number of pairs such that at least one digit is common in between them.

Eg. For 5 numbers :

2837 2818 654 35 931

Answer : 6

The pairs here are (2837,2818), (2837,35), (2837,931), (2818,931), (654,35), (35,931)

My Attempt : I took a structure which stores the number in decimal, the number in form of its digits in array and number of digits in that number.

Now for each number I hashed that number in array conatining index 0-9 and the checked with all following numbers wether any of their digit is already present.

My attempt is O(n^2), which is slow. Is there another algorithm that will work faster?

algorithm
Edit
Report