| 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) is 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 : no of test cases (T >= 1 && T <= 7)
For each test case, you will be given two lines, first line will contain n <= 10^6
then in next n line each line will contain a single integer representing a[i] (a[i] >= 1 && a[i] <= 10^18)
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-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! :) |
||||||
|
2013-09-11 07:05:33 nitish rao
@praveen123 can you plz check my sol. um getting WA.. :( sol-id:9929488 got AC :) Last edit: 2013-08-28 10:04:51 |
||||||
RSS