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!
2 Likes
Thx for your reply shivam .
Can u please explain it more.