# Hamming Distance

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

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

```#pragma comprint(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#define LL __int64
#define FIN freopen("in.txt","r",stdin)
using namespace std;
const int MAXN=100000+5;
const int MAX=1<<21;
const int INF=0x3f3f3f3f;
int a[MAX+5],num[MAXN];
int kase,n;
void init()
{
for(int i=0;i<=MAX;i++)
{
int cnt=0;
for(int j=0;j<21;j++)
if(i & (1<<j))
cnt++;
a[i]=cnt;
}
}
int main()
{
init();
scanf("%d",&kase);
while(kase--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%x",&num[i]);
int ans=INF;
srand( (unsigned)time( NULL ) );
for(int i=0;i<900000;i++)
{
int x=rand()%n;
int y=rand()%n;
if(x==y) continue;
ans=min(ans,a[num[x]^num[y]]);
}
printf("%d\n",ans);
}
return 0;
}```

## hdu 4712 Hamming Distance（随机数法）

d.汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量, 我们以d(x,y)表示两个字x,y之间的汉明距离.对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离. 给出N个串,求出其中最小的汉明距离(其中某2个串的汉明距离是最小的). s.随机数法... c.能不能过,看脸... #include<iostream> #include<stdio.h> #include<string.h> #inc

## hduoj 4712 Hamming Distance 2013 ACM/ICPC Asia Regional Online —— Warmup

http://acm.hdu.edu.cn/showproblem.php?pid=4712 Hamming Distance Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 1610    Accepted Submission(s): 630 Problem Description (From wikipedia) For bina

## 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note:0 ≤ x, y < 2^31. Example: Input: x = 1, y = 4 Output: 2 Explanation:

## 461. Hamming Distance（leetcode）

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note:0 ≤ x, y < 2^31. Example: Input: x = 1, y = 4 Output: 2 Explanation:

## 461. Hamming Distance【数学|位运算】

2017/3/14 15:23:55 The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. 题目要求:求两个数字二进制位中同一位置不同bit的个数. 解法1  Java    利用1的移位依次匹配是否对

## 相似算法 ，Java实例9 - 汉明距离 Hamming Distance

Java实例9 - 汉明距离 Hamming Distance http://blog.csdn.net/kindterry/article/details/6581344 /**在信息理论中,两个等长字符串之间的汉明距离 * 是两个字符串对应位置上不同字符的个数, * 换句话说,汉明距离就是将一个字符串替换成另外一个字符串所需要替换的字符长度. *例如,1011101和1001001之间的汉明距离是2, *toned和roses之间的汉明距离是3. *汉明重量是字符串相对于同样长度的零字符串的

## 729 - The Hamming Distance Problem

// 题意: // 输入两个整数N, H,按照字典序输出所有长度为N,恰好包含H个1的01串 // 规模:1<=H<=N<=16 // 算法A:2^N枚举,输出1的个数为H的.采用递归枚举 // 从bits[d]开始确定,已经用了c0个0和c1个1 #include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm>

## LeetCode解题思路：461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note:0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1