# Hamming Distance

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 916    Accepted Submission(s): 335

Problem Description

(From wikipedia) For binary strings a and b the Hamming distance is equal to the number of ones in a XOR b. For calculating Hamming distance between two strings a and b, they must have equal length. Now given N different binary strings, please calculate the minimum Hamming distance between every pair of strings.

Input

The first line of the input is an integer T, the number of test cases.(0<T<=20) Then T test case followed. The first line of each test case is an integer N (2<=N<=100000), the number of different binary strings. Then N lines followed, each of the next N line is a string consist of five characters. Each character is '0'-'9' or 'A'-'F', it represents the hexadecimal code of the binary string. For example, the hexadecimal code "12345" represents binary string "00010010001101000101".

Output

For each test case, output the minimum Hamming distance between every pair of strings.

Sample Input

2

2

12345

54321

4

12345

6789A

BCDEF

0137F

Sample Output

6

7

Source

2013 ACM/ICPC Asia Regional Online —— Warmup

随机算法，第一次接触......

/*
ussigned dist(unsigned a, unsigned b)
{
int val=a^b,da=0;
while(val)
{
val ^= val -1;
da++;
}
return 0;
}
*/

 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<ctime>
5 #include<algorithm>
6 #define maxn 100000
7 using namespace std;
8 int dist(int a,int b)   //gongshi
9 {
10     int val=a^b,distance=0;
11     while(val)
12     {
13         ++distance;
14         val &= val - 1 ;
15     }
16  return distance;
17 }
18 int Hex[maxn+1];
19 int main()
20 {
21     int t,i,n,min,x,y,c,cnt;
22 //time_t t1;
23     scanf("%d",&t);
24     while(t--)
25     {
26      scanf("%d",&n);
27      for(i=0;i<n;i++)
28      scanf("%X",&Hex[i]);
29         srand((unsigned)time(NULL));
30      for(cnt=i=0;i<maxn;i++)
31      {
32          x=rand()%n;
33          y=rand()%n;
34          if(x!=y)
35          {
36            c=dist(Hex[x],Hex[y]);
37            if(cnt==0||min>c)
38               min=c,cnt=1;
39            else
40                 if(min==0) break;
41          }
42      }
43      printf("%d\n",min);
44     }
45  return 0;
46 }

0 条评论

## 相关文章

48160

47480

366120

### 大数据时代商业银行的策略

尽管大数据对商业银行的影响目前而言还比较小，但从发展趋势看，要充分认识大数据的颠覆性影响。各银行必须未雨绸缪，早做布局，从管理体系建设、具体运用模式方面不...

432130

37250

### 老码农拍着脑袋总结的法子

1.扎实的基础。数据结构、离散数学、编译原理，这些是所有计算机科学的基础，如果不掌握他们，很难写出高水平的程序。据我的观察，学计算机专业的人比学其他专业的人更能...

394150

30280

438120

62360

51970