Hamming distance - Method 1

Software Development
#1

Method #1:

Create another array which is double the size of the original array, such that the elements of this new array (copy array) are just the elements of the original array repeated twice in the same sequence. Example, if the original array is 1 4 1, then the copy array is 1 4 1 1 4 1.
Now, iterate through the copy array and find hamming distance with every shift (or rotation). So we check 4 1 1, 1 1 4, 1 4 1, choose the output for which the hamming distance is maximum.
Below is the implementation of above approach:

  • C++

// C++ program to Find another array

// such that the hamming distance

// from the original array is maximum

#include <bits/stdc++.h>

using namespace std;

// Return the maximum hamming distance of a rotation

int maxHamming( int arr[], int n)

{

`` // arr[] to brr[] two times so that

`` // we can traverse through all rotations.

`` int brr[2 *n + 1];

`` for ( int i = 0; i < n; i++)

`` brr[i] = arr[i];

`` for ( int i = 0; i < n; i++)

`` brr[n+i] = arr[i];

`` // We know hamming distance with 0 rotation

`` // would be 0.

`` int maxHam = 0;

`` // We try other rotations one by one and compute

`` // Hamming distance of every rotation

`` for ( int i = 1; i < n; i++)

`` {

`` int currHam = 0;

`` for ( int j = i, k=0; j < (i + n); j++,k++)

`` if (brr[j] != arr[k])

`` currHam++;

`` // We can never get more than n.

`` if (currHam == n)

`` return n;

`` maxHam = max(maxHam, currHam);

`` }

`` return maxHam;

}

// driver program

int main()

{

`` int arr[] = {2, 4, 6, 8};

`` int n = sizeof (arr)/ sizeof (arr[0]);

`` cout << maxHamming(arr, n);

`` return 0;

}

Output:

4

Time Complexity : O(n*n)

Move to part 2, Method 2 for more.