Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is Hamming Distance?
1.2.
Problem statement
1.3.
Sample Examples
2.
Brute Force Approach  
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach  
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions 
4.1.
How many bit operations are done in finding the Hamming distance?
4.2.
Can we change the size of the array at runtime? 
4.3.
What is the time complexity of swapping two elements in an array?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find a rotation with maximum hamming distance

Author Tarun Singh
0 upvote

Introduction

This blog will try to strengthen our understanding of a single-dimensional Array data structure problem. We will try to understand how to approach any array data structure problem through that problem. The examples presented will help you clear your concepts, a detailed algorithm will provide you with an immediate solution, and the implementation part will give you a thorough understanding of every step. So, let's get started with the problem statement and some quick examples. 

What is Hamming Distance?

The number of locations at which the corresponding characters (elements) differ between two arrays or strings of identical length is known as the Hamming distance. To determine the Hamming distance, count the number of bits that differ between two arrays of the same size. The hamming distance between 1101 and 1001 is 1.

Problem statement

Firstly, we will have a look at what exactly the problem says. Given an array of 'n' elements. In that array, we have to find a rotation with maximum hamming distance.

Sample Examples

Example 1:

Input:

n=5, Array- nums[]= {2,4,5,2,3}

 

Output:

The maximum hamming distance is: 5
One of the arrays with which the hamming distance would be 5 is {3,5,2,4,2}.

 

Example 2:


 Input:

 n=4, Array- nums[]= {4,6,4,6}

 

Output: 

The maximum hamming distance is: 4 
One of the arrays with which the hamming distance would be 4 is {6,4,6,4}.

Brute Force Approach  

In the brute force approach, we create a new array that is twice the size of the old array, with the elements of this new array being the original array's elements repeated twice in the same order. We go through the copy array in each rotation and find the hamming distance.

Algorithm

  • Define the size of the array, and take input for the size.
  • Define the array of the size taken in input, and take input for the elements of the array.
  • We define an array hamm_a[2 * size + 1] and make a copy of the array.
  • We initialize a variable for max_value with an initial value 0.
  • We loop through the copied array and check for maximum hamming distance.
  • The outer loop runs from the first index to (size-1)the index. And in the internal loop, we check for hamming distance.
  • We print the result we get while performing the code mentioned above.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int main()
{ // initializing the size of input array
    int size;
    cin >> size;
    int a[size];
    int x = 0;
    // input for array elements
    for (int i = 0; i < size; i++)
    {
        cin >> a[i];
    }
    // making the copy of array
    int li = 2 * size + 1;
    int hamm_a[li];
    for (int i = 0; i < size; i++)
    {
        hamm_a[i] = a[i];
        hamm_a[size + i] = a[i];
    }

    int max_val = 0;

    // outer loop which runs from 1 to the size variable
    for (int i = 1; i < size; i++)
    {
        int Init_val = 0;
        int j = i, k = 0;
        // inner loop which runs from i to i+size
        for (; j < (i + size); j++, k++)
            if (hamm_a[j] != a[k])
                Init_val++;

        if (Init_val == size)
        {
            cout << "The maximum hamming distance is:" << size << endl;
            x = 0;
            break;
        }

        max_val = max(max_val, Init_val);
    }

    // printing the answer
    if (x)
        cout << "The maximum hamming distance is: " << max_val << endl;
}

 

Input:

 n=5, a[]={6,7,5,6,4}

 

Output:

THe maximum hamming distance is: 5

 

Complexity Analysis

Time Complexity: The time complexity will be O(n^2) as we take two loops one inside another to find the hamming distance.

Space Complexity: The space complexity will be O(n) as we created an extra array to copy array elements.

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach  

In this optimized approach, the elements of the original array sequence will be compared against their rotated versions. The arrays are rotated using the shifted index method, which compares elements at the original index with elements at the shifted index without taking up any additional space. This approach brings down the space complexity to O(1).

Algorithm

  • Define the size of the array, and take input for the size.
  • Define the array of the size taken in input, and take input for the elements of the array.
  • We will initialize and run a for loop from the first index to the last element.
  • In the inner for loop, we compare the original array and the rotated version.
  • For the rotation of the array element, we have used shifted index method; in this method, we compare array elements at the rotated index and original index. 
     
    for (int i = 0; i < size; i++) //inner loop
    {
         if (a[i] != a[(i + j) % size]) //comparison 
            hamming_dist++;
    } 

 

  • The point of using this method is that we don't require extra space to store the copy of the array.
  • We print the result obtained from performing the above operations.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // input the size
    int size;
    cin >> size;
    int a[size];
    bool flag = true;
    // input the array
    for (int i = 0; i < size; i++)
    {
        cin >> a[i];
    }

    int hamming_dist;
    // outer loop which runs from 1 to the size of the array
    for (int j = 1; j < size; j++)
    {
        hamming_dist = 0;
        
        // inner loop which runs from 0 to the size of the array
        for (int i = 0; i < size; i++)
        {
            if (a[i] != a[(i + j) % size])
                hamming_dist++;
        }
        if (hamming_dist == size)
        {
            flag = false;
            cout << "The hamming distance is: " << size;
            break;
        }
    }
    if (flag)
    {
        cout << "The hamming distance is: " <<  hamming_dist << endl;
    }
}

 

Input:

n=6, 
arr[]={1, 6, 2, 4, 6, 6}

 

Output:

The maximum hamming distance is: 5

 

Complexity Analysis

Time Complexity: The time complexity will be O(n^2) as we use two loops one inside the other to find the hamming distance.

Space Complexity: The space complexity will be O(1) as we did not use an extra array to copy the array elements.

Frequently Asked Questions 

How many bit operations are done in finding the Hamming distance?

Two-bit operations are done in finding hamming distance. The Hamming distance is a statistic that can be used to compare two binary data strings. Hamming distance is the number of bit positions in which the two bits differ when comparing two binary strings of equal length.

Can we change the size of the array at runtime? 

The array's size is determined at the time of its creation or initialization. The array's size cannot be changed once it has been created. Even so, if you try to assign a value to a member of the array that is larger than its size, a runtime exception will be thrown.

What is the time complexity of swapping two elements in an array?

It takes a constant time complexity to swap two elements of an array. We just maintain a temp variable to swap the elements and no loop is taken in action.

Conclusion

In this article, we have analyzed how to find a rotation with maximum hamming distance. We have gone through two different approaches to solving the problem; we have also discussed their algorithm, C++ code, and also their space and time complexity. 

After reading about this array problem, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn, see Data Structures and AlgorithmsCompetitive Programming.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating SystemUnix File System, File Input/Output.JavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass