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
hide comments
|
praveen123:
2013-09-11 07:05:33
@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.
|
|
Mitch Schwartz:
2013-09-11 07:05:33
@praveen123: Please check the formatting according to numerix's comment. Last edit: 2013-09-11 03:34:24 |
|
Mayank Raj:
2013-09-11 07:05:33
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.
|
|
Rishabh Sharma:
2013-09-11 07:05:33
Very nice problem!!! :) |
|
numerix:
2013-09-11 07:05:33
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 Schwartz:
2013-09-11 07:05:33
@numerix: Every number is friends with itself, and the answer for your test case is 1. |
|
|
numerix:
2013-09-11 07:05:33
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?
|
|
$iddharth prasad:
2013-09-11 07:05:33
can someone give some more test cases plzz ... |
|
Ouditchya Sinha:
2013-09-11 07:05:33
Awesome problem! :) |
|
nitish rao:
2013-09-11 07:05:33
@praveen123 can you plz check my sol. um getting WA.. :( sol-id:9929488
|
| 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 |
RSS