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 no of pairs which are friends.
(Formally speaking Let us assume the n numbers be 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.).
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)
For every test case print a line
containing number of such pairs as mentioned in the problem statement.
10 12 24
5 6 7
10 11 211 3
Downvoted for TL preventing submissions in slower languages, albeit from the comments I infer it's the fault of the SPOJ code recalculating limits after compiler update rather than psetters. With dataset containing a million numbers per case, O(n^2) would obviously fail at far more relaxed limit.
nice problem with best concept;
Same as http://www.spoj.com/problems/KOMPICI/
nyc problem.... learnt a lot :)
learned something new :)
will O(n2) pass?
considering a[i] as a string of size 25 got AC...in 0.53 sec..where as considering a[i] as a long long data type got AC in 1.78 sec...Can anyone justify the reason for this weird behavior...????
TLE..taking input as string and using printf and scanf. help??
I remember this question was a part of Directi coding contest for hiring at MNNIT Allahabad.