No of triplets which have common digit

We have an Array of size N , we have to find out no of triplets (i,j,k) in the array A, with i < j < k such that the triplets have ateast one prime digit in common.

1 ≤ N ≤ 10^5
0 ≤ A[i] ≤ 10^18 for all index i in the array A.
Can any one help me how to do this .

You can solve this using Inclusion Exclusion Principle…

Now the prime digits are 2,3,5 and 7… So if u maintain a count of the number of numbers with a particular set of prime digits (null,{2},{3},{5},{7},{2,3},…,{2,3,5,7}) , there will be 16 sets in all…
cnt[i] denote the number of numbers which have all the numbers in the ith set as its digits…

Then the answer can be calculated as:

ans=0

for(int i=1;i<=15;i++){

if(number of set bits in i is odd){

ans+=nC3(cnt[i])

}

else{

ans-=nC3(cnt[i])

}

}

The above conecpt is actually related to the Union Concept of Set Theory!

Here is my soln based on the above concept : http://www.hackerearth.com/submission/496682/

Happy Coding! :slight_smile:

2 Likes

Thx for your reply shivam .
Can u please explain it more.

//