All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Mehta and the Tricky Triplets
/

Bit manipulation, Bitmask, Dynamic Programming, Mathematics

Problem
Editorial
Analytics

Mehta is a forever alone and desperate guy. He has a crush on N girls of his society. He wants to impress them all and so he needs to do their task collectively.All the girls give him a number which he stores in an array named A of size N. To do their task, he has to report the number of triplets \((i,j,k)\) in the array A, with i < j < k such that the triplets have at least one prime digit in common.

Input & Output:

The first line of the input contains an integer N. The next N lines has a number on each, which denote the array A.

You need to print on one line, the number of triples with the condition mentioned in the problem statement.

Constraints:

\(1 \le N \le 10 ^ 5\)
\(0 \le A[i] \le 10 ^ {18} \) for all index i in the array A.

Sample Input:

5 21 22 23 24 25

Sample Output:
10

SAMPLE INPUT
5
21
22
23
24
25
SAMPLE OUTPUT
10
Explanation

In the given sample each \(i,j,k\) has one prime digit common that is 2. So, total triplets are \(5C3\) which is \(10\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?