advertisement
Login | Register   
  Include Code  Search Tips
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   TIP BANK
Browse DevX
Partners & Affiliates
advertisement
advertisement

Problem Statement: Hamming Distance

    

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

Back to TopCoder Challenge Page

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is trictly prohibited. (c)2005, TopCoder, Inc. All rights reserved.

advertisement