Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Saturday, February 22, 2014

IITKWPCH-Find Number Of Pair of Friends

Find Number Of Pair of Friends

given below code is for iitkwpch spoj & find number of pair of friends spoj
in 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
now its decimal will be 2 so i will increament the array a at position two
& for 35

0 0 0 0 1 0 1 0 0 0
its decimal is 40 so i will increament the array a[] at position 40;

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;
#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;
}