Dada una array de N elementos, cree una nueva array que es una rotación de la array dada, y la distancia de hamming entre ambas arrays es máxima. La tarea es imprimir la distancia de hamming maximizada entre arrays dadas y nuevas.
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.
Ejemplos:
Entrada: N = 3, arr = {1, 4, 1}
Salida: 2
Explicación: Posibles rotaciones de la array dada = 4 1 1 y 1 1 4. En cada caso, la distancia de hamming es 2. Por lo tanto, la distancia de hamming máxima será 2.Entrada: N = 4, arr = {2, 4, 8, 0}
Salida: 4
Explicación: Entre las rotaciones posibles de una array dada, las rotaciones 8 0 2 4 y 0 2 4 8 tienen la distancia máxima de hamming de 4.
Enfoque ingenuo:
La idea es crear otra array que tenga el doble del tamaño de la array original, de modo que los elementos de esta nueva array (array de copia) sean solo los elementos de la array original repetidos dos veces en la misma secuencia. Por ejemplo, si la array original es 1 4 1, entonces la array de copia es 1 4 1 1 4 1. Ahora, itere a través de la array de copia y encuentre la distancia de Hamming con cada cambio (o rotación). Entonces verificamos 4 1 1, 1 1 4, 1 4 1, y elegimos la salida para la cual la distancia de hamming es máxima.
Ilustración:
Dada la array arr[]={2, 4, 6, 8}.
Nueva array brr[]={2, ,4, 6, 8, 2, 4, 6, 8} , contar=0
- En la primera iteración: { 2 , 4, 6, 8} & {2 , 4 , 6, 8, 2, 4, 6, 8} , cuenta=1
- En la segunda iteración: {2, 4 , 6, 8} y {2, 4, 6 , 8, 2, 4, 6, 8}, cuenta = 2
- En la tercera iteración: {2,4, 6 , 8} & {2,4, 6, 8 , 2, 4, 6, 8}, cuenta=3
- En cuarta iteración: {2,4, 6, 8 } & {2,4, 6, 8, 2 , 4, 6, 8}, cuenta=4
- cuenta = tamaño de la array original, por lo tanto, la salida es 4
Implementación:
Crearemos otra array del doble del tamaño de la array original e insertaremos los elementos en ella uno por uno, dos veces. Ahora realizaremos la rotación en la array y para cada rotación, verificaremos si el valor de la array original coincide con la array recién creada.
- Si no coinciden, aumentaremos el valor de nuestro contador.
- Después de que se incremente el valor, realizaremos una condición para verificar el valor máximo, para controlar el valor máximo que se puede obtener.
- De lo contrario, si los valores no coinciden, no tenemos que realizar ninguna operación.
- Dentro del ciclo de verificación, también tendremos que mantener una verificación si el valor de contador = tamaño de la array original, ya que es el valor máximo que podemos obtener. Si la condición coincide, podemos devolver el valor. Esta condición optimiza nuestro código.
A continuación se muestra la implementación del código del enfoque anterior:
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];
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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to Find another array such that the hamming
// distance from the original array is maximum
#include <stdio.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
// 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];
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]);
printf("%d\n", maxHamming(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to Find another array
// such that the hamming distance
// from the original array is maximum
class GFG
{
// Return the maximum hamming
// distance of a rotation
static int maxHamming(int arr[], int n)
{
// arr[] to brr[] two times so that
// we can traverse through all rotations.
int brr[]=new int[2 *n + 1];
for (int i = 0; i < n; i++){
brr[i] = arr[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 = Math.max(maxHam, currHam);
}
return maxHam;
}
// driver code
public static void main (String[] args)
{
int arr[] = {2, 4, 6, 8};
int n = arr.length;
System.out.print(maxHamming(arr, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 code to Find another array # such that the hamming distance # from the original array is maximum # Return the maximum hamming # distance of a rotation def maxHamming( arr , n ): # arr[] to brr[] two times so # that we can traverse through # all rotations. brr = [0] * (2 * n + 1) for i in range(n): brr[i] = arr[i] for i in range(n): brr[n+i] = arr[i] # We know hamming distance # with 0 rotation would be 0. maxHam = 0 # We try other rotations one by # one and compute Hamming # distance of every rotation for i in range(1, n): currHam = 0 k = 0 for j in range(i, i + n): if brr[j] != arr[k]: currHam += 1 k = k + 1 # We can never get more than n. if currHam == n: return n maxHam = max(maxHam, currHam) return maxHam # driver program arr = [2, 4, 6, 8] n = len(arr) print(maxHamming(arr, n)) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# program to Find another array
// such that the hamming distance
// from the original array is maximum
using System;
class GFG {
// Return the maximum hamming
// distance of a rotation
static int maxHamming(int []arr, int n)
{
// arr[] to brr[] two times so that
// we can traverse through all rotations.
int []brr=new int[2 * n + 1];
for (int i = 0; i < n; i++){
brr[i] = arr[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 = Math.Max(maxHam, currHam);
}
return maxHam;
}
// driver code
public static void Main ()
{
int []arr = {2, 4, 6, 8};
int n = arr.Length;
Console.Write(maxHamming(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to Find another array
// such that the hamming distance
// from the original array is maximum
// Return the maximum hamming
// distance of a rotation
function maxHamming($arr, $n)
{
// arr[] to brr[] two times so that
// we can traverse through all rotations.
$brr = array();
for ($i = 0; $i < $n; $i++)
$brr[$i] = $arr[$i];
for ($i = 0; $i < $n; $i++)
$brr[$n+$i] = $arr[$i];
// We know hamming distance
// with 0 rotation would be 0.
$maxHam = 0;
// We try other rotations one
// by one and compute Hamming
// distance of every rotation
for ($i = 1; $i < $n; $i++)
{
$currHam = 0;
for ( $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 Code
$arr = array(2, 4, 6, 80);
$n = count($arr);
echo maxHamming($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to Find another array
// such that the hamming distance
// from the original array is maximum
// Return the maximum hamming distance of a rotation
function maxHamming(arr, n)
{
// arr[] to brr[] two times so that
// we can traverse through all rotations.
let brr = new Array(2 *n + 1);
for (let i = 0; i < n; i++){
brr[i] = arr[i];
brr[n+i] = arr[i];
}
// We know hamming distance with 0 rotation
// would be 0.
let maxHam = 0;
// We try other rotations one by one and compute
// Hamming distance of every rotation
for (let i = 1; i < n; i++)
{
let currHam = 0;
for (let 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
let arr = [2, 4, 6, 8];
let n = arr.length;
document.write(maxHamming(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
4
Complejidad de tiempo: O(n 2 ), donde n es el tamaño de la array dada
Espacio auxiliar: O(n)
Enfoque 2 (en espacio constante):
La idea es comparar elementos de la secuencia de array original con sus versiones rotadas. Las versiones rotadas de la array se logran mediante el método de índice desplazado en el que se comparan elementos en el índice original con elementos en el índice desplazado, sin necesidad de espacio adicional.
Ilustración:
Dada la array arr[]={2, 4, 6, 8}. cuenta=0. Usaremos la operación de módulo para comparar los dos índices diferentes de la misma array.
- En la primera iteración: { 2 , 4, 6, 8} & {2 , 4 , 6, 8} , cuenta=1
- En la segunda iteración: {2, 4 , 6, 8} y {2, 4, 6 , 8}, cuenta = 2
- En la tercera iteración: {2,4, 6 , 8} y {2,4, 6, 8 }, cuenta = 3
- En cuarta iteración: {2,4, 6, 8 } & {2,4 , 6, 8}, cuenta=4
- cuenta = tamaño de la array original, por lo tanto, la salida es 4
Siga los pasos a continuación para la idea anterior:
Realizaremos la rotación en la array y para cada rotación, verificaremos si el valor de la array en cualquier índice i coincide con el valor del índice j. Donde j determina la rotación e i como el índice real para el cual se debe realizar la comparación.
- j = 1,2,3 … , n-1 & i= 0, 1, 2 , … ,n-1, n es el tamaño de nuestra array.
- Si arr[i] no es igual a arr[(i+j)%n] aumentaremos el valor de nuestro contador
- De lo contrario, si los valores no coinciden, no tenemos que realizar ninguna operación.
- Dentro del ciclo de verificación, también tendremos que mantener una verificación si el valor de contador = tamaño de la array original , ya que es el valor máximo que podemos obtener. Si la condición coincide, podemos devolver el valor. Esta condición optimiza nuestro código.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find another array
// such that the hamming distance
// from the original array is maximum
// requires O(n*n) time and O(1) extra space;
#include <bits/stdc++.h>
using namespace std;
// Return the maximum hamming distance of a rotation
int maxHamming(int arr[], int n){
int hmmd;
// outer loop for how much rotation
for(int j = 1; j < n; j++){
hmmd = 0;
//inner loop to compare elements with elements on shifted index
for(int i = 0 ; i < n; i++){
if(arr[i] != arr[(i + j) % n])
hmmd++;
}
//max possible hamming distance is n, no need to check further
if(hmmd == n)
return n;
}
return hmmd;
}
// driver program
int main()
{
int arr[] = {2, 4, 6, 8};
int n = sizeof(arr)/sizeof(arr[0]);
cout << maxHamming(arr, n);
return 0;
}
// This method is contributed by nehalrandive
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Java program to Find another array
// such that the hamming distance
// from the original array is maximum
// requires O(n*n) time and O(1) extra space;
// Return the maximum hamming distance of a rotation
static int maxHamming(int arr[], int n){
int hmmd = 0;
// outer loop for how much rotation
for(int j = 1; j < n; j++){
hmmd = 0;
// inner loop to compare elements with elements on shifted index
for(int i = 0 ; i < n; i++){
if(arr[i] != arr[(i + j) % n])
hmmd++;
}
// max possible hamming distance is n, no need to check further
if(hmmd == n)
return n;
}
return hmmd;
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 4, 6, 8};
int n = arr.length;
System.out.println(maxHamming(arr, n));
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program to Find another array # such that the hamming distance # from the original array is maximum # requires O(n*n) time and O(1) extra space; # Return the maximum hamming distance of a rotation def maxHamming(arr, n): # outer loop for how much rotation hmmd = 0 for j in range(1,n): hmmd = 0 #inner loop to compare elements with elements on shifted index for i in range(n): if(arr[i] != arr[(i + j) % n]): hmmd += 1 #max possible hamming distance is n, no need to check further if(hmmd == n): return n return hmmd # driver program arr = [2, 4, 6, 8] n = len(arr) print(maxHamming(arr, n)) # This code is contributed by shinjanpatra
C#
// C# program to Find another array
// such that the hamming distance
// from the original array is maximum
// requires O(n*n) time and O(1) extra space;using System;
using System;
class GFG
{
// Return the maximum hamming distance of a rotation
static int maxHamming(int[] arr, int n)
{
int hmmd = 0;
// outer loop for how much rotation
for (int j = 1; j < n; j++)
{
hmmd = 0;
// inner loop to compare elements with elements on shifted index
for (int i = 0; i < n; i++)
{
if (arr[i] != arr[(i + j) % n])
hmmd++;
}
// max possible hamming distance is n, no need to check further
if (hmmd == n)
return n;
}
return hmmd;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 4, 6, 8 };
int n = arr.Length;
Console.Write(maxHamming(arr, n));
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// JavaScript program to Find another array
// such that the hamming distance
// from the original array is maximum
// requires O(n*n) time and O(1) extra space;
// Return the maximum hamming distance of a rotation
function maxHamming(arr, n){
let hmmd;
// outer loop for how much rotation
for(let j = 1; j < n; j++){
hmmd = 0;
//inner loop to compare elements with elements on shifted index
for(let i = 0 ; i < n; i++){
if(arr[i] != arr[(i + j) % n])
hmmd++;
}
//max possible hamming distance is n, no need to check further
if(hmmd == n)
return n;
}
return hmmd;
}
// driver program
let arr = [2, 4, 6, 8];
let n = arr.length;
document.write(maxHamming(arr, n),"</br>");
// This method is contributed by shinjanpatra
</script>
Producción
4
Complejidad de tiempo: O(n 2 ), donde n es el tamaño de la array dada
Espacio auxiliar: O(1)
Enfoque 3 (utilizando la comprensión de listas):
Podemos encontrar la distancia máxima de hamming usando un enfoque diferente aprovechando la comprensión de listas en python. En este método, dividimos el trabajo en 3 funciones separadas.
- hamming_distance(x : lista, y : lista): Este método devuelve la distancia de hamming para dos listas pasadas como parámetros. La idea es contar las posiciones en las que los elementos son diferentes en el mismo índice en dos listas x e y, donde x es la array original tomada en la entrada e y es una de sus rotaciones.
- Inicializar un conteo variable desde 0.
- Ejecute un bucle desde el índice inicial 0 hasta el último índice (n-1), donde n es la longitud de la lista.
- Para cada iteración, compruebe si el elemento de x y el elemento en el índice i (0<=i<=n-1) son iguales o no. Si son iguales, incrementa el contador.
- Una vez que se completa el ciclo, devuelva el conteo (por definición, esta es la distancia de hamming para arrays o strings dadas)
- rotar_por_uno(arr : lista): Este método rota la array (pasada en el argumento) en dirección contraria a las manecillas del reloj por 1 posición. Por ejemplo, si se pasa la array [1,1,4,4], este método devuelve [1,4,4,5,1].
- La idea es copiar el primer elemento de la array y guardarlo en una variable (por ejemplo, x).
- Luego itere la array de 0 a n-2 y copie cada valor i+1 en la posición i. Ahora asigne x al último índice.
- max_hamming_distance(arr: list): este método encuentra la distancia máxima de hamming para una array dada y sus rotaciones. Siga los pasos a continuación en este método.
- Copiamos esta array en una nueva array (digamos a) e inicializamos una variable max.
- Ahora, después de cada n rotaciones, obtenemos la array original. Entonces, necesitamos encontrar la distancia de hamming para la array original con sus rotaciones n-1 y almacenar el máximo actual en una variable (digamos max).
- Ejecutar bucle para n-1 iteraciones. Para cada iteración.
Siga los pasos a continuación para la idea anterior:
- Obtenga la próxima rotación de arr llamando al método ‘rotate_by_one’.
- Llame al método hamming distance() y pase una array original (a) y la rotación actual de un (arr) y almacene la distancia hamming actual devuelta en una variable (por ejemplo, curr_h_dist).
- Compruebe si el valor de curr_h_dist es mayor que el valor de max. En caso afirmativo, asigne el valor de curr_h_dist a max_h.
- Repita los pasos 1-3 hasta que termine el ciclo.
- Distancia máxima de hamming de retorno (max_h)
A continuación se muestra la implementación de la idea anterior:
Python3
# Python code to find maximum
# of an array with it's rotations
import time
# Function hamming distance to find
# the hamming distance for two lists/strings
def hamming_distance(x: list, y: list):
# Initialize count
count = 0
# Run loop for size of x(or y)
# as both as same length
for i in range(len(x)):
# Check if corresponding elements
# at same index are not equal
if(x[i] != y[i]):
# Increment the count every
# time above condition satisfies
count += 1
# Return the hamming distance
# for given pair of lists or strings
return count
# Function to rotate the given array
# in anti-clockwise direction by 1
def rotate_by_one(arr: list):
# Store 1st element in a variable
x = arr[0]
# Update each ith element (0<=i<=n-2)
# with it's next value
for i in range(0, len(arr)-1):
arr[i] = arr[i+1]
# Assign 1st element to the last index
arr[len(arr)-1] = x
# Function max_hamming_distance to find
# the maximum hamming distance for given array
def max_hamming_distance(arr: list):
# Initialize a variable to store
# maximum hamming distance
max_h = -10000000000
# Store size of the given array
# in a variable n
n = len(arr)
# Initialize a new array
a = []
# Copy the original array in new array
for i in range(n):
a.append(arr[i])
# Run loop for i=0 to i=n-1 for n-1 rotations
for i in range(1, n):
# Find the next rotation
rotate_by_one(arr)
print("Array after %d rotation : " % (i), arr)
# Store hamming distance of current
# rotation with original array
curr_h_dist = hamming_distance(a, arr)
print("Hamming Distance with %d rotations: %d" %
(i, curr_h_dist))
# Check if current hamming distance
# is greater than max hamming distance
if curr_h_dist > max_h:
# If yes, assign value of current
# hamming distance to max hamming distance
max_h = curr_h_dist
print('\n')
# Return maximum hamming distance
return max_h
# Driver code
if __name__ == '__main__':
arr = [3, 0, 6, 4, 3]
start = time.time()
print('\n')
print("Original Array : ", arr)
print('\n')
print("Maximum Hamming Distance: ", max_hamming_distance(arr))
end = time.time()
print(f"Execution Time = {end - start}")
# This code is contributed by Vivek_Kumar_Sinha
Producción
Original Array : [3, 0, 6, 4, 3] Array after 1 rotation : [0, 6, 4, 3, 3] Hamming Distance with 1 rotations: 4 Array after 2 rotation : [6, 4, 3, 3, 0] Hamming Distance with 2 rotations: 5 Array after 3 rotation : [4, 3, 3, 0, 6] Hamming Distance with 3 rotations: 5 Array after 4 rotation : [3, 3, 0, 6, 4] Hamming Distance with 4 rotations: 4 Maximum Hamming Distance: 5 Execution Time = 6.985664367675781e-05