Given an integer array arr[]. Create a new array which is a rotation of given array and find the maximum Hamming distance between both the arrays.
Hamming distance between two arrays or strings of equal length is the number of positions at which the corresponding character(elements) are different.
Note: There can be more than one output for the given input.
Example:
Input: arr[] = [1, 4, 1]
Output: 2
Explanation: Maximum hamming distance = 2, this hamming distance with 4 1 1 or 1 1 4
Input: arr[] = [2, 4, 8, 0]
Output: 4
Explanation: Maximum hamming distance = 4, this hamming distance with 4 8 0 2. All the places can be occupied by another digit. Other solutions can be 8 0 2 4, 4 0 2 8 etc.
Approach: This problem can be solved efficiently by using the Hashmap. Follow the steps given below to solve the problem
- Iterate through the array arr[] and store the values of the array in a HashMap <key, value>. Value can be List<> or string depending on interest.
- Add the value in hashmap, hashMap.add(arrvalue, list).
- Check this condition:
- When the hashMap.contains(arrValue) then hashmap.get(arrayValue).append(index).
- Check the size of the hashmap, if size == 1 then
- max hamming distance = 0. Because all values are the same.
- Run the for each loop, for each key if the list size = 1 then
- max hamming distance = n. Because all values are diff.
- Create an array of size – 1 of the given array for storing the similar occurrences that can happen.
- After storing all the indexes of array store the values in hashMap.
- For each difference found a += 1. This difference says the number of rotations it would take to have the same value in the same position.
- Find the least value in the array and get the index => min same values => max hamming distance.
Below is the implementation of the above approach:
C++
// Find a rotation with maximum hamming distance#include<bits/stdc++.h>using namespace std;// Function to return the min valueint getMinValue(vector<int> numbers){ // var to store the min value int minValue = numbers[0]; for(int i = 1; i < numbers.size(); i++) { // Condition to check if value is // lesser from the minValue or not if (numbers[i] < minValue) { minValue = numbers[i]; } } // Return the minValue return minValue;}// Function to get the hamming distanceint maxHammingDistance(vector<int> array){ int n = array.size(); vector<int> repetitionsOnRotations(n - 1,0); // Create the map to store the key value pair map<int, vector<int>> indexesOfElements; for(int i = 0; i < n; i++) { int key = array[i]; // Take empty list of integers // to store the integer vector<int>indexes; if (indexesOfElements.find(key) != indexesOfElements.end()) { indexes = indexesOfElements[key]; } else { indexes.clear(); } // Add the value in list index indexes.push_back(i); indexesOfElements[key] = indexes; } // Run the for loop and get the // value from hash map one at a time for(auto x : indexesOfElements) { vector<int> indexes = x.second; for(int i = 0; i < indexes.size() - 1; i++) { for(int j = i + 1; j < indexes.size(); j++) { // Store the diff into the variable int diff = indexes[i] - indexes[j]; // Check the condition if diff // is less than zero or not if (diff < 0) { repetitionsOnRotations[-diff - 1] += 1; diff = n + diff; } repetitionsOnRotations += 1; } } } // Return the hamming distance return n - getMinValue(repetitionsOnRotations);}// Driver codeint main(){ // Example 1 vector<int> array{ 1, 4, 1 }; int result1 = maxHammingDistance(array); cout << result1 << endl; // Example 2 vector<int> array2{ 2, 4, 8, 0 }; int result2 = maxHammingDistance(array2); cout << result2 << endl;}// This code is contributed by ipg2016107 |
Java
// Find a rotation with maximum hamming distanceimport java.io.*;import java.util.*;class GFG { // Function to return the min value public static int getMinValue(int[] numbers) { // var to store the min value int minValue = numbers[0]; for (int i = 1; i < numbers.length; i++) { // Condition to check if value is // lesser from the minValue or not if (numbers[i] < minValue) { minValue = numbers[i]; } } // Return the minValue return minValue; } // Function to get the hamming distance public static int maxHammingDistance(int[] array) { int n = array.length; int[] repetitionsOnRotations = new int[n - 1]; // Create the map to store the key value pair Map<Integer, List<Integer> > indexesOfElements = new HashMap<>(); for (int i = 0; i < n; i++) { int key = array[i]; // Take empty list of integers // to store the integer List<Integer> indexes = null; if (indexesOfElements.containsKey(key)) { indexes = indexesOfElements.get(key); } else { indexes = new ArrayList<>(); } // Add the value in list index indexes.add(i); indexesOfElements.put(key, indexes); } // Run the for loop and get the // value from hash map one at a time for (Map.Entry<Integer, List<Integer> > keys : indexesOfElements.entrySet()) { List<Integer> indexes = keys.getValue(); for (int i = 0; i < indexes.size() - 1; i++) { for (int j = i + 1; j < indexes.size(); j++) { // Store the diff into the variable int diff = indexes.get(i) - indexes.get(j); // Check the condition if diff // is less than zero or not if (diff < 0) { repetitionsOnRotations[(-diff) - 1] += 1; diff = n + diff; } repetitionsOnRotations += 1; } } } // Return the hamming distance return n - (getMinValue(repetitionsOnRotations)); } // Driver code public static void main(String[] args) { // Example 1 int[] array = { 1, 4, 1 }; int result1 = GFG.maxHammingDistance(array); System.out.println(result1); // Example 2 int[] array2 = { 2, 4, 8, 0 }; int result2 = GFG.maxHammingDistance(array2); System.out.println(result2); }} |
Python3
# Find a rotation with maximum hamming distance# Function to return the min valuedef getMinValue(numbers): # var to store the min value minValue = numbers[0] for i in range(1, len(numbers)): # Condition to check if value is # lesser from the minValue or not if (numbers[i] < minValue): minValue = numbers[i] # Return the minValue return minValue# Function to get the hamming distancedef maxHammingDistance(array): n = len(array) repetitionsOnRotations = [0] * (n - 1) # Create the map to store the key value pair indexesOfElements = {} for i in range(n): key = array[i] # Take empty list of integers # to store the integer indexes = [] if (key in indexesOfElements): indexes = indexesOfElements[key] else: indexes = [] # Add the value in list index indexes.append(i) indexesOfElements[key] = indexes # Run the for loop and get the # value from hash map one at a time for indexes in indexesOfElements.values(): for i in range(len(indexes) - 1): for j in range(i + 1, len(indexes)): # Store the diff into the variable diff = indexes[i] - indexes[j] # Check the condition if diff # is less than zero or not if (diff < 0): repetitionsOnRotations[-diff - 1] += 1 diff = n + diff repetitionsOnRotations += 1 # Return the hamming distance return n - getMinValue(repetitionsOnRotations)# Driver code# Example 1array = [1, 4, 1]result1 = maxHammingDistance(array)print(result1)# Example 2array2 = [2, 4, 8, 0]result2 = maxHammingDistance(array2)print(result2)# This code is contributed by _saurabh_jaiswal |
C#
// Find a rotation with maximum hamming distanceusing System;using System.Collections.Generic;class GFG{// Function to return the min valuepublic static int getMinValue(int[] numbers){ // var to store the min value int minValue = numbers[0]; for(int i = 1; i < numbers.Length; i++) { // Condition to check if value is // lesser from the minValue or not if (numbers[i] < minValue) { minValue = numbers[i]; } } // Return the minValue return minValue;}// Function to get the hamming distancepublic static int maxHammingDistance(int[] array){ int n = array.Length; int[] repetitionsOnRotations = new int[n - 1]; // Create the map to store the key value pair Dictionary<int, List<int>> indexesOfElements = new Dictionary<int, List<int>>(); for(int i = 0; i < n; i++) { int key = array[i]; // Take empty list of integers // to store the integer List<int> indexes = null; if (indexesOfElements.ContainsKey(key)) { indexes = indexesOfElements[key]; } else { indexes = new List<int>(); } // Add the value in list index indexes.Add(i); if (!indexesOfElements.ContainsKey(key)) indexesOfElements.Add(key, indexes); } // Run the for loop and get the // value from hash map one at a time foreach(KeyValuePair<int, List<int>> keys in indexesOfElements) { List<int> indexes = keys.Value; for(int i = 0; i < indexes.Count - 1; i++) { for(int j = i + 1; j < indexes.Count; j++) { // Store the diff into the variable int diff = indexes[i] - indexes[j]; // Check the condition if diff // is less than zero or not if (diff < 0) { repetitionsOnRotations[(-diff) - 1] += 1; diff = n + diff; } repetitionsOnRotations += 1; } } } // Return the hamming distance return n - (getMinValue(repetitionsOnRotations));}// Driver codepublic static void Main(String[] args){ // Example 1 int[] array = { 1, 4, 1 }; int result1 = GFG.maxHammingDistance(array); Console.WriteLine(result1); // Example 2 int[] array2 = { 2, 4, 8, 0 }; int result2 = GFG.maxHammingDistance(array2); Console.WriteLine(result2);}}// This code is contributed by umadevi9616 |
Javascript
<script>// Find a rotation with maximum hamming distance// Function to return the min valuefunction getMinValue(numbers){ // var to store the min value let minValue = numbers[0]; for(let i = 1; i < numbers.length; i++) { // Condition to check if value is // lesser from the minValue or not if (numbers[i] < minValue) { minValue = numbers[i]; } } // Return the minValue return minValue;}// Function to get the hamming distancefunction maxHammingDistance(array){ let n = array.length; let repetitionsOnRotations = new Array(n - 1).fill(0); // Create the map to store the key value pair let indexesOfElements = new Map(); for(let i = 0; i < n; i++) { let key = array[i]; // Take empty list of integers // to store the integer let indexes = []; if (indexesOfElements.has(key)) { indexes = indexesOfElements.get(key); } else { indexes = []; } // Add the value in list index indexes.push(i); indexesOfElements.set(key, indexes); } // Run the for loop and get the // value from hash map one at a time for(let keys of indexesOfElements) { let indexes = keys[1]; for(let i = 0; i < indexes.length - 1; i++) { for(let j = i + 1; j < indexes.length; j++) { // Store the diff into the variable let diff = indexes[i] - indexes[j]; // Check the condition if diff // is less than zero or not if (diff < 0) { repetitionsOnRotations[-diff - 1] += 1; diff = n + diff; } repetitionsOnRotations += 1; } } } // Return the hamming distance return n - getMinValue(repetitionsOnRotations);}// Driver code// Example 1let array = [ 1, 4, 1 ];let result1 = maxHammingDistance(array);document.write(result1 + "<br>");// Example 2let array2 = [ 2, 4, 8, 0 ];let result2 = maxHammingDistance(array2);document.write(result2);// This code is contributed by gfgking</script> |
Output:
2 4
Time complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!