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.