Encuentre una rotación con la máxima distancia de hamming | conjunto 2

Dada una array de enteros arr[] . Cree una nueva array que sea una rotación de la array dada y encuentre la distancia máxima de Hamming entre ambas arrays.

La distancia de Hamming entre dos arrays o strings de igual longitud es el número de posiciones en las que los caracteres (elementos) correspondientes son diferentes .

Nota: Puede haber más de una salida para la entrada dada.

Ejemplo:

Entrada: arr[] = [1, 4, 1] 

Salida: 2 

Explicación: Distancia máxima de hamming = 2, esta distancia de hamming con 4 1 1 o 1 1 4   

Entrada: arr[] = [2, 4, 8, 0] 

Salida: 4 

Explicación: Distancia máxima de hamming = 4, esta distancia de hamming con 4 8 0 2. Todos los lugares pueden ser ocupados por otro dígito. Otras soluciones pueden ser 8 0 2 4, 4 0 2 8 etc.  
 

Enfoque: este problema se puede resolver de manera eficiente utilizando Hashmap . Siga los pasos que se indican a continuación para resolver el problema.

• Itere a través de la array arr[] y almacene los valores de la array en un HashMap <key, value> . El valor puede ser Lista<> o string según el interés.
• Agregue el valor en hashmap, hashMap.add(arrvalue, list).
• Compruebe esta condición:
  • Cuando hashMap.contains(arrValue) entonces hashmap.get(arrayValue).append(index).
• Verifique el tamaño del hashmap, si el tamaño == 1 , entonces
  • distancia máxima de hamming = 0 . Porque todos los valores son iguales.
• Ejecute for each loop, for each key si el tamaño de la lista = 1 entonces
  • distancia máxima de hamming = n . Porque todos los valores son diferentes.
• Cree una array de tamaño: 1 de la array dada para almacenar las ocurrencias similares que pueden ocurrir.
• Después de almacenar todos los índices de la array, almacene los valores en hashMap .
• Para cada diferencia encontrada un += 1 . Esta diferencia dice el número de rotaciones que se necesitarían para tener el mismo valor en la misma posición.
• Encuentre el valor mínimo en la array y obtenga el índice => valores mínimos iguales => distancia máxima de hamming.

A continuación se muestra la implementación del enfoque anterior:

// Find a rotation with maximum hamming distance
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the min value
int getMinValue(vector<int> numbers)
{
     
    // var to stor 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 distance
int 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 then 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
int 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

// Find a rotation with maximum hamming distance
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to return the min value
    public static int getMinValue(int[] numbers)
    {
 
        // var to stor 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 then 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);
    }
}

# Find a rotation with maximum hamming distance
 
# Function to return the min value
def getMinValue(numbers):
 
    # var to stor 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 distance
def 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 then 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 1
array = [1, 4, 1]
result1 = maxHammingDistance(array)
print(result1)
 
# Example 2
array2 = [2, 4, 8, 0]
result2 = maxHammingDistance(array2)
print(result2)
 
# This code is contributed by _saurabh_jaiswal

// Find a rotation with maximum hamming distance
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the min value
public static int getMinValue(int[] numbers)
{
     
    // var to stor 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
    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 then 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);
    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

<script>
 
// Find a rotation with maximum hamming distance
 
// Function to return the min value
function getMinValue(numbers)
{
     
    // var to stor 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 distance
function 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 then 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 1
let array = [ 1, 4, 1 ];
let result1 = maxHammingDistance(array);
document.write(result1 + "<br>");
 
// Example 2
let array2 = [ 2, 4, 8, 0 ];
let result2 = maxHammingDistance(array2);
document.write(result2);
 
// This code is contributed by gfgking
 
</script>

2
4

Complejidad temporal: O(N)
Espacio auxiliar: O(N)