TopCoder problem "HammingDistance" used in SRM 272 (Division II Level One)



Problem Statement

    

The Hamming distance between two numbers is defined as the number of positions in their binary representations at which they differ (leading zeros are used if necessary to make the binary representations have the same length) - e.g., the numbers "11010" and "01100" differ at the first, third and fourth positions, so they have a Hamming distance of 3.

You will be given a String[] numbers containing the binary representations of some numbers (all having the same length). You are to return the minimum among the Hamming distances of all pairs of the given numbers.

 

Definition

    
Class:HammingDistance
Method:minDistance
Parameters:String[]
Returns:int
Method signature:int minDistance(String[] numbers)
(be sure your method is public)
    
 

Constraints

-numbers will have between 2 and 50 elements, inclusive.
-Each element of numbers will have between 1 and 50 characters, inclusive.
-All elements of numbers will have the same number of characters.
-All elements of numbers will only contain the characters '0' and '1'.
 

Examples

0)
    
{"11010", "01100"}
Returns: 3

The example from the problem statement.

1)
    
{"00", "01", "10", "11"}
Returns: 1

A binary code that uses all possible codewords has minimum Hamming distance 1.

2)
    
{"000", "011", "101", "110"}
Returns: 2

Adding a "parity bit" to the binary numbers of example 1 increases the minimum Hamming distance to 2.

3)
    
{"01100", "01100", "10011"}
Returns: 0

Note that the input may contain identical numbers (Hamming distance 0).

4)
    
{"00000000000000000000000000000000000000000000000000",
"11111111111111111111111111111111111111111111111111"}
Returns: 50
5)
    
{"000000", "000111", "111000", "111111"}
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5884

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8069&pm=5884

Writer:

gepa

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, String Parsing