Dada una array arr[] de N enteros no negativos y un entero P (1 ≤ P ≤ 30) , que indica que el límite superior de cualquier número en la array es (2 P – 1) . La tarea es encontrar un número tal que la suma de las distancias de Hamming entre el número en sí y todos los números de la array sea mínima. Si hay varias respuestas posibles, imprima cualquiera de ellas.
Nota: La distancia de Hamming entre dos números es el número de posiciones en su representación binaria en las que los bits de los números son diferentes
Ejemplos:
Entrada: N = 4, P = 4
arr[] = {12, 11, 8, 10}
Salida: 8
Explicación: El número 8 tiene una suma mínima de distancias de Hamming.
Distancia de Hamming desde 12: 1
Distancia de Hamming desde 11: 2
Distancia de Hamming desde 8: 0
Distancia de Hamming desde 10: 1
10 también puede ser una respuesta válida.Entrada: N = 3, P = 3
arr[] = {5, 2, 7}
Salida: 7
Enfoque: este problema se puede resolver utilizando el enfoque codicioso y la manipulación de bits . Con la observación, se puede decir que en la respuesta final, solo se establecerán aquellos bits que tengan un mayor número de 1 para todos los elementos de la array en comparación con los 0. Porque de lo contrario, la suma total de diferentes bits aumentará. Siga los pasos que se mencionan a continuación para resolver el problema:
- Cree una array 2D bits[][] para contar los bits de todos los números en cada una de las posiciones de bit P.
- Comience a iterar la array desde el principio.
- Para cada elemento de la array, aumente el recuento de bits para cada bit establecido en la array bits[][] .
- Una vez finalizada la iteración, compruebe el número total de bits establecidos en la array de bits .
- Si el número de bits establecidos en una posición es mayor que el número de 0 en esa posición de bit, establezca ese bit en el número resultante como 1, de lo contrario como 0.
- Devuelve el número final como resultado.
Ilustración:
Por ejemplo, tome la array, arr[] = {12, 11, 8, 10} y P = 4 .
Ahora vea la representación de bits de los números en la siguiente imagen:
Representación lógica
En la imagen de arriba se puede ver claramente que el bit menos significativo tiene más 0 en comparación con 1.
De manera similar, el tercer bit y el bit más significativo tienen más números 0 y 1 respectivamente.
Pero el segundo bit tiene el mismo número de 0 y 1.
Entonces, el número resultante puede tener representación binaria 1010 o 1000, es decir, puede ser 10 u 8.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to find a number y such that
// sum of hamming distance between y
// and all the numbers given in array
// is minimum
#include <bits/stdc++.h>
using namespace std;
// Function to find the number
int findNum(int arr[], int P, int N)
{
// Creating the bits 2D array
int bits[N + 1][P + 1];
// Setting each column as 0 in row 0
// to ensure proper
// addition for all i upto n
for (int i = 0; i < P; i++)
bits[0][i + 1] = 0;
// Filling the bits array
for (int i = 0; i < N; i++) {
int j = 1;
// For each bit from 1 to P
for (int k = 1; k <= P; k++) {
int temp = arr[i];
int x = 0;
// If kth bit is set in temp
// set x = 1 else x as 0
if (temp & j)
x = 1;
// If kth bit is set
// add x = 1 to previous value
// in the same column
bits[i + 1][k] = bits[i][k] + x;
// Left shift j to check next bit
j = j << 1;
}
}
// x here is the bit contribution
// in decimal
int x = 1;
// Declare variable to store answer
int y = 0;
// For each bit in the last row
// check the count of 1s.
for (int i = 1; i <= P; i++) {
// If numbers of 1s is greater than
// number of 0s then add
// that bit's contribution to y
// else do not add anything
if (bits[N][i] > N / 2)
y += x;
// multiply x by 2 each time to get
// the new bit value as at bit 0
// value is 2^0 at bit 1 it
// is 2^1, at bit 2 is 2^2 and so on
x *= 2;
}
return y;
}
// Driver code
int main()
{
int N = 4, P = 4;
// Declaring the array
int arr[N] = { 12, 11, 8, 10 };
int ans = findNum(arr, P, N);
cout << ans;
return 0;
}
Java
// Java code to find a number y such that
// sum of hamming distance between y
// and all the numbers given in array
// is minimum
class GFG {
// Function to find the number
static int findNum(int[] arr, int P, int N) {
// Creating the bits 2D array
int[][] bits = new int[N + 1][P + 1];
// Setting each column as 0 in row 0
// to ensure proper
// addition for all i upto n
for (int i = 0; i < P; i++)
bits[0][i + 1] = 0;
// Filling the bits array
for (int i = 0; i < N; i++) {
int j = 1;
// For each bit from 1 to P
for (int k = 1; k <= P; k++) {
int temp = arr[i];
int x = 0;
// If kth bit is set in temp
// set x = 1 else x as 0
if ((temp & j) != 0)
x = 1;
// If kth bit is set
// add x = 1 to previous value
// in the same column
bits[i + 1][k] = bits[i][k] + x;
// Left shift j to check next bit
j = j << 1;
}
}
// x1 here is the bit contribution
// in decimal
int x1 = 1;
// Declare variable to store answer
int y = 0;
// For each bit in the last row
// check the count of 1s.
for (int i = 1; i <= P; i++) {
// If numbers of 1s is greater than
// number of 0s then add
// that bit's contribution to y
// else do not add anything
if (bits[N][i] > N / 2)
y += x1;
// multiply x by 2 each time to get
// the new bit value as at bit 0
// value is 2^0 at bit 1 it
// is 2^1, at bit 2 is 2^2 and so on
x1 *= 2;
}
return y;
}
// Driver code
public static void main(String args[]) {
int N = 4, P = 4;
// Declaring the array
int[] arr = { 12, 11, 8, 10 };
int ans = findNum(arr, P, N);
System.out.println(ans);
}
}
// This code is contributed by gfgking
Python3
# Python program to implement # the above approach # Function to find the number def findNum(arr, P, N) : # Creating the bits 2D array bits = [[0] * (N + 1)] * (P + 1) # Setting each column as 0 in row 0 # to ensure proper # addition for all i upto n for i in range(0, P) : bits[0][i + 1] = 0 # Filling the bits array for i in range(N) : j = 1 # For each bit from 1 to P for k in range(1, P+1) : temp = arr[i] x = 0 # If kth bit is set in temp # set x = 1 else x as 0 if (temp & j) : x = 1 # If kth bit is set # add x = 1 to previous value # in the same column bits[i + 1][k] = bits[i][k] + x # Left shift j to check next bit j = j << 1 # x here is the bit contribution # in decimal x = 1 # Declare variable to store answer y = 0 # For each bit in the last row # check the count of 1s. for i in range(1, P+1) : # If numbers of 1s is greater than # number of 0s then add # that bit's contribution to y # else do not add anything if (bits[N][i] > N / 2) : y += x # multiply x by 2 each time to get # the new bit value as at bit 0 # value is 2^0 at bit 1 it # is 2^1, at bit 2 is 2^2 and so on x *= 2 return y # Driver code N = 4 P = 4 # Declaring the array arr = [ 12, 11, 8, 10 ] ans = findNum(arr, P, N) print(ans) # This code is contributed by sanjoy_62.
C#
// C# code to find a number y such that
// sum of hamming distance between y
// and all the numbers given in array
// is minimum
using System;
class GFG
{
// Function to find the number
static int findNum(int[] arr, int P, int N)
{
// Creating the bits 2D array
int[, ] bits = new int[N + 1, P + 1];
// Setting each column as 0 in row 0
// to ensure proper
// addition for all i upto n
for (int i = 0; i < P; i++)
bits[0, i + 1] = 0;
// Filling the bits array
for (int i = 0; i < N; i++) {
int j = 1;
// For each bit from 1 to P
for (int k = 1; k <= P; k++) {
int temp = arr[i];
int x = 0;
// If kth bit is set in temp
// set x = 1 else x as 0
if ((temp & j) != 0)
x = 1;
// If kth bit is set
// add x = 1 to previous value
// in the same column
bits[i + 1, k] = bits[i, k] + x;
// Left shift j to check next bit
j = j << 1;
}
}
// x1 here is the bit contribution
// in decimal
int x1 = 1;
// Declare variable to store answer
int y = 0;
// For each bit in the last row
// check the count of 1s.
for (int i = 1; i <= P; i++) {
// If numbers of 1s is greater than
// number of 0s then add
// that bit's contribution to y
// else do not add anything
if (bits[N, i] > N / 2)
y += x1;
// multiply x by 2 each time to get
// the new bit value as at bit 0
// value is 2^0 at bit 1 it
// is 2^1, at bit 2 is 2^2 and so on
x1 *= 2;
}
return y;
}
// Driver code
public static int Main()
{
int N = 4, P = 4;
// Declaring the array
int[] arr = new int[4] { 12, 11, 8, 10 };
int ans = findNum(arr, P, N);
Console.Write(ans);
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code for the above approach
// Function to find the number
function findNum(arr, P, N)
{
// Creating the bits 2D array
let bits = new Array(N + 1);
for (let i = 0; i < N + 1; i++) {
bits[i] = new Array(P + 1);
}
// Setting each column as 0 in row 0
// to ensure proper
// addition for all i upto n
for (let i = 0; i < P; i++)
bits[0][i + 1] = 0;
// Filling the bits array
for (let i = 0; i < N; i++) {
let j = 1;
// For each bit from 1 to P
for (let k = 1; k <= P; k++) {
let temp = arr[i];
let x = 0;
// If kth bit is set in temp
// set x = 1 else x as 0
if (temp & j)
x = 1;
// If kth bit is set
// add x = 1 to previous value
// in the same column
bits[i + 1][k] = bits[i][k] + x;
// Left shift j to check next bit
j = j << 1;
}
}
// x here is the bit contribution
// in decimal
let x = 1;
// Declare variable to store answer
let y = 0;
// For each bit in the last row
// check the count of 1s.
for (let i = 1; i <= P; i++) {
// If numbers of 1s is greater than
// number of 0s then add
// that bit's contribution to y
// else do not add anything
if (bits[N][i] > Math.floor(N / 2))
y += x;
// multiply x by 2 each time to get
// the new bit value as at bit 0
// value is 2^0 at bit 1 it
// is 2^1, at bit 2 is 2^2 and so on
x *= 2;
}
return y;
}
// Driver code
let N = 4, P = 4;
// Declaring the array
let arr = [12, 11, 8, 10];
let ans = findNum(arr, P, N);
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
8
Tiempo Complejidad: O(N * P)
Espacio Auxiliar: O(N * P)
Publicación traducida automáticamente
Artículo escrito por siddharthsinghvats y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA