HammingDistance
SRM 272 · 2005-11-19 · by gepa
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
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'.
{"11010", "01100"}
Returns: 3
The example from the problem statement.
{"00", "01", "10", "11"}
Returns: 1
A binary code that uses all possible codewords has minimum Hamming distance 1.
{"000", "011", "101", "110"}
Returns: 2
Adding a "parity bit" to the binary numbers of example 1 increases the minimum Hamming distance to 2.
{"01100", "01100", "10011"}
Returns: 0
Note that the input may contain identical numbers (Hamming distance 0).
{"00000000000000000000000000000000000000000000000000",
"11111111111111111111111111111111111111111111111111"}
Returns: 50
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HammingDistance with a public method int minDistance(vector<string> numbers) · 90 test cases · 2 s / 256 MB per case