### Find Number Of Pair of Friends

given below code is for iitkwpch spoj & find number of pair of friends spojin the given problem two number are friend if two number have atlest two digit in common.

now i have taken an array of size 10 and initalize it with all zero now i am scaning number and if any digit is encountered then then i will make array element 1 at that position

eg:

for number 11 there is two 1 so make 1 at position 1;

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

& for 35

0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |

now i am pairing for digit occurance of number in two nested for loop I have started with position 0

of i & j; condition is given i<j so and not to check number with itself and condition (i & j) is for that if number have atleast one common digit or not

eg

for position 35 and 11

condition (35 & 11) will be false because number are having no common digit

in single for loop i am checking occurence of sane number if given condition is

1

10

1 1 1 1 1 1 1 1 1 1

then possible pairs are n(n-1)/2;

since the two nested loop is reversely repeated so all pairs will occure wice so in last i am dividing it by 2;

in single for loop i am checking occurence of sane number if given condition is

1

10

1 1 1 1 1 1 1 1 1 1

then possible pairs are n(n-1)/2;

since the two nested loop is reversely repeated so all pairs will occure wice so in last i am dividing it by 2;

#include <stdio.h> #include <iostream> #include <cstdlib> #define LL long long using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,i,j,num=0; scanf("%d",&n); LL temp,total=0; LL *a=(LL *)calloc(1200,sizeof(LL)); int dig[10]={0}; while(n--) { scanf("%lld",&temp); while(temp) { num=num | (1<<temp%10); temp/=10; } a[num]++; num=0; } for(i=1;i<1024;i++) { for(j=1;j<1024;j++) { if(i!=j && (i&j)){ total+=a[i]*a[j]; } } } for(i=1;i<1024;i++) total+=(a[i]*(a[i]-1)); printf("%lld\n",total/2); } return 0; }