| Submit | All submissions | Best solutions | Back to list |
IITKWPCH - Find Number Of Pair of Friends |
You are given n numbers. Any two number are called friends if they have some digit common. eg. (11, 12) and (15, 4561) are friends but (33, 556) are not.
Find out the number of pairs which are friends.
(Formally speaking let us suppose the n numbers are stored in array a[]. You have to find out number of i and j pairs such that i < j and a[i] and a[j] are friends.)
Input
T : number of test cases (1 ≤ T ≤ 7)
For each test case, you will be given two lines, first line will contain n <= 106, then the next line will contain n integers representing a[i] (1 ≤ a[i] ≤ 1018.)
Output
For every test case print a line containing number of such pairs as mentioned in the problem statement.
Example
Input: 4 2 12 13 3 10 12 24 3 5 6 7 4 10 11 211 3 Output: 1 2 0 3
| Added by: | praveen123 |
| Date: | 2013-08-05 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | general problem |
hide comments
|
||||||
|
2013-12-26 14:05:12 Piyush Kapoor
I remember this question was a part of Directi coding contest for hiring at MNNIT Allahabad. |
||||||
|
2013-09-11 07:05:33 praveen123
@Mayank, My completely unoptimized code in c++ took 0.5 sec. So I chose the time limit to 1 sec. If you are using some other language other than C,C++ then I can agree with your point but not with C,C++ for sure. Increasing time limit to 2 sec. |
||||||
|
2013-09-11 07:05:33 Mitch Schwartz
@praveen123: Please check the formatting according to numerix's comment. Last edit: 2013-09-11 03:34:24 |
||||||
|
2013-09-11 07:05:33 Mayank Raj
This question is not in the programming spirit! The time limit should be extended...provided you are running on a SILLY PENTIUM 3 machine...less than the computational power of an average smartphone. I had to struggle till eternity to optimize on the constants of the time complexity... The time limit should be such that THE CORRECT algorithm's descent implementation should work! |
||||||
|
2013-09-11 07:05:33 Rishabh Sharma
Very nice problem!!! :) |
||||||
|
2013-09-11 07:05:33 numerix
The input data is malformatted, which cost me a lot of WAs! The given number of values per line does not match with the real number of values per line. @Mitch: Thanks for clarification. So my initial algorithm was correct, but the successive WAs made me confused. |
||||||
|
2013-09-11 07:05:33 Mitch Schwartz
@numerix: Every number is friends with itself, and the answer for your test case is 1. |
||||||
|
2013-09-11 07:05:33 numerix
What is the exact meaning of "any two numbers"? Does that imply that those "two numbers" have to be different numbers? So, is the correct output for the following example 1 or 0? 1 2 3 3 |
||||||
|
2013-09-11 07:05:33 $iddharth prasad
can someone give some more test cases plzz ... |
||||||
|
2013-09-11 07:05:33 Ouditchya Sinha
Awesome problem! :) |
||||||
RSS