Encuentre un número con la menor suma de diferencias de bits de la array dada

Posted on by Rudeus Greyrat

Dada una array arr[] y un número entero L que representa el número de bits a considerar en la representación de bits de un elemento de array. La tarea es encontrar un entero positivo X , tal que la suma de la diferencia de bits de todos los elementos en arr[] con X sea mínima.

Ejemplos:

Entrada: N = 3, L = 5, arr[] = {18, 9, 21}
Salida: 17
Explicación: arr[1] = (18) 10 = (10010) 2 , arr[2] = (9) 10 = (01001) 2 , arr[3] = (21) 10 = (10101) 2 
Suponga que X = (17) 10 = (10001) 2 .
Diferencia entre arr[1] y X : 2 (Diferentes bits en el índice 3 y 4)
Diferencia entre arr[2] y X : 2 (Diferentes bits en el índice 0 y 1)
Diferencia entre arr[3] y X : 1 (Diferente bits en el índice 2)
Por lo tanto, si X = 17, la suma de las diferencias de bits será 2 + 2 +1 = 5, que es el mínimo posible.

Entrada: N = 3, L = 5 y arr[] = {8, 8, 8}
Salida: 8 

 

Enfoque: Este problema se puede resolver usando la siguiente idea:

  • En la posición de bit i, el bit en la X resultante debe ser el mismo que el bit mayoritario en la i-ésima posición de todos los elementos del Array.
  • Esto se puede lograr usando Hashing .

Ilustración:

Supongamos que la array es {5, 6, 4} 

Representación de bits de array:
5 = 101
6 = 110
4 = 100

Ahora encontremos la X usando el bit de mayoría posicional de Array:
En la posición 1: mayoría (1, 1, 1) = 1
En la posición 2: mayoría (0, 1, 0) = 0
En la posición 3: mayoría (1, 0, 0) = 0

Por lo tanto X formado = 100 = 4

Ahora encontremos la diferencia de bits de X con elementos de array:
BitDiferencia (X, 5) = BitDiferencia (100, 101) = 1
BitDiferencia (X, 6) = BitDiferencia (100, 110) = 1
BitDiferencia (X, 4) = BitDiferencia (100, 100) = 0

Suma de diferencias de bits = 2, que será la menor posible. 
 

Siga los pasos a continuación para resolver el problema dado. 

  • Inicialice una frecuencia de array de longitud L que mantenga la pista del número de bits establecidos en cada posición en cada elemento de array dado.
  • Iterar la frecuencia y si la frecuencia del i -ésimo índice es mayor que N/2 , mantenga el bit establecido en el número requerido.
  • Si la frecuencia del i -ésimo índice es menor que N/2 , mantenga el bit apagado en el número requerido.
  • Convierta el número binario formado en un número decimal y devuelva el valor.
  • Imprime el resultado final

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

C++

// C++ program for above approach
 
#include <iostream>
using namespace std;
 
// Function to find number
// having smallest difference
// with N numbers
int smallestDifference(int N, int L, int arr[])
{
    // Initializing freq array
    // which keeps tracks of
    // number of set bits at every index
    int freq[L] = { 0 };
 
    // Making freq map of set bits
    for (int i = 0; i < L; i++) {
 
        // Traversing every element
        for (int j = 0; j < N; j++) {
 
            // If bit is on then
            // updating freq array
            if ((arr[j] & 1) > 0) {
                freq[i]++;
            }
            arr[j] >>= 1;
        }
    }
 
    // Converting binary form of needed
    // number into decimal form
    int number = 0;
    int p = 1;
 
    // Traversing freq array
    for (int i = 0; i < L; i++) {
 
        // If frequency of set bit
        // is greater than N/2
        // then we have to keep it set
        // in our answer
        if (freq[i] > N / 2) {
            number += p;
        }
        p *= 2;
    }
 
    // Returning numbers
    // having smallest difference
    // among N given numbers
    return number;
}
// Driver Code
int main()
{
    int N = 3;
    int L = 5;
    int arr[] = { 18, 9, 21 };
 
    // Function call
    int number = smallestDifference(N, L, arr);
    cout << number << endl;
    return 0;
}

Java

// Java program for above approach
 
import java.util.*;
 
class GFG {
 
    // Function to find number
    // having smallest difference
    // with N numbers
    public static int smallestDifference(int N, int L,
                                         int[] arr)
    {
        // Initializing freq array
        // which keeps tracks of
        // number of set bits at every index
        int[] freq = new int[L];
 
        // Making freq map of set bits
        for (int i = 0; i < L; i++) {
 
            // Traversing every element
            for (int j = 0; j < N; j++) {
 
                // If bit is on then
                // updating freq array
                if ((arr[j] & 1) > 0) {
                    freq[i]++;
                }
                arr[j] >>= 1;
            }
        }
 
        // Converting binary form of needed
        // number into decimal form
        int number = 0;
        int p = 1;
 
        // Traversing freq array
        for (int i = 0; i < L; i++) {
 
            // If frequency of set bit
            // is greater than N/2
            // then we have to keep it set
            // in our answer
            if (freq[i] > N / 2) {
                number += p;
            }
            p *= 2;
        }
 
        // Returning numbers
        // having smallest difference
        // among N given numbers
        return number;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 3;
        int L = 5;
        int[] arr = { 18, 9, 21 };
 
        // Function call
        int number = smallestDifference(N, L, arr);
        System.out.println(number);
    }
}

Python

# Python program for above approach
 
# Function to find number
# having smallest difference
# with N numbers
def smallestDifference(N, L, arr):
 
    # Initializing freq array
    # which keeps tracks of
    # number of set bits at every index
    freq = []
    for i in range(0, L):
        freq.append(0)
 
    # Making freq map of set bits
    for i in range(0, L):
 
        # Traversing every element
        for j in range(0, N):
 
            # If bit is on then
            # updating freq array
            if ((arr[j] & 1) > 0):
                freq[i] += 1
 
            arr[j] >>= 1
 
    # Converting binary form of needed
    # number into decimal form
    number = 0
    p = 1
 
    # Traversing freq array
    for i in range(0, L):
 
        # If frequency of set bit
        # is greater than N/2
        # then we have to keep it set
        # in our answer
        if (freq[i] > N // 2):
            number += p
 
        p *= 2
 
    # Returning numbers
    # having smallest difference
    # among N given numbers
    return number
 
# Driver Code
N = 3
L = 5
arr = [18, 9, 21]
 
# Function call
number = smallestDifference(N, L, arr)
print(number)
 
# This code is contributed by Samim Hossain Mondal.

C#

using System;
 
public class GFG{
 
  // Function to find number
  // having smallest difference
  // with N numbers
  public static int smallestDifference(int N, int L,
                                       int[] arr)
  {
    // Initializing freq array
    // which keeps tracks of
    // number of set bits at every index
    int[] freq = new int[L];
 
    // Making freq map of set bits
    for (int i = 0; i < L; i++) {
 
      // Traversing every element
      for (int j = 0; j < N; j++) {
 
        // If bit is on then
        // updating freq array
        if ((arr[j] & 1) > 0) {
          freq[i]++;
        }
        arr[j] >>= 1;
      }
    }
 
    // Converting binary form of needed
    // number into decimal form
    int number = 0;
    int p = 1;
 
    // Traversing freq array
    for (int i = 0; i < L; i++) {
 
      // If frequency of set bit
      // is greater than N/2
      // then we have to keep it set
      // in our answer
      if (freq[i] > N / 2) {
        number += p;
      }
      p *= 2;
    }
 
    // Returning numbers
    // having smallest difference
    // among N given numbers
    return number;
  }
 
  // Driver Code
  static public void Main ()
  {
    int N = 3;
    int L = 5;
    int[] arr = { 18, 9, 21 };
 
    // Function call
    int number = smallestDifference(N, L, arr);
    Console.Write(number);
  }
}
 
// This code is contributed by hrithikgarg03188.

Javascript

<script>
// Javascript program for above approach
 
// Function to find number
// having smallest difference
// with N numbers
function smallestDifference(N, L, arr)
{
 
    // Initializing freq array
    // which keeps tracks of
    // number of set bits at every index
    let freq = [];
    for(let i = 0; i < L; i++) {
        freq[i] = 0;
    }
 
    // Making freq map of set bits
    for (let i = 0; i < L; i++) {
 
        // Traversing every element
        for (let j = 0; j < N; j++) {
 
            // If bit is on then
            // updating freq array
            if ((arr[j] & 1) > 0) {
                freq[i]++;
            }
            arr[j] >>= 1;
        }
    }
 
    // Converting binary form of needed
    // number into decimal form
    let number = 0;
    let p = 1;
 
    // Traversing freq array
    for (let i = 0; i < L; i++) {
 
        // If frequency of set bit
        // is greater than N/2
        // then we have to keep it set
        // in our answer
        if (freq[i] > N / 2) {
            number += p;
        }
        p *= 2;
    }
 
    // Returning numbers
    // having smallest difference
    // among N given numbers
    return number;
}
 
// Driver Code
let N = 3;
let L = 5;
let arr = [ 18, 9, 21 ];
 
// Function call
let number = smallestDifference(N, L, arr);
document.write(number);
 
// This code is contributed by Samim Hossain Mondal.
</script>
Producción

17

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

Publicación traducida automáticamente

Artículo escrito por Kdheeraj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *