Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número mínimo de bits de los elementos de la array necesarios para invertirlos para que todos los elementos de la array sean iguales .
Ejemplos:
Entrada: arr[] = {3, 5}
Salida: 2
Explicación:
A continuación se muestran los bits de los elementos de array necesarios:
- Para el elemento arr[0](= 3): voltear el tercer bit desde la derecha modifica arr[0] a (= 7(111) 2 ). Ahora, la array se convierte en {7, 5}.
- Para el elemento arr[0](= 7): Voltear el segundo bit desde la derecha modifica arr[0] a 5 (= (101) 2 ). Ahora, la array se convierte en {5, 5}.
Después de realizar las operaciones anteriores, todos los elementos de la array son iguales. Por lo tanto, el número total de cambios de bits requeridos es 2.
Entrada: arr[] = {4, 6, 3, 4, 5}
Salida: 5
Enfoque: el problema dado se puede resolver modificando el elemento de la array de tal manera que el número de bits activados y desactivados en cada posición entre todos los elementos de la array. Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays de frecuencia, digamos fre0[] y fre1[] de tamaño 32 para contar la frecuencia de 0 y 1 para cada bit de los elementos de la array.
- Recorra la array dada y para cada elemento de la array, arr[i] si el j -ésimo bit de arr[i] es un bit establecido , luego incremente la frecuencia de fre1[j] en 1 . De lo contrario, incremente la frecuencia de fre0[j] en 1 .
- Después de completar los pasos anteriores, imprima la suma del mínimo de fre0[i] y fre1[i] para cada bit i sobre el rango [0, 32] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum number
// of bits required to be flipped
// to make all array elements equal
int makeEqual(int* arr, int n)
{
// Stores the count of unset bits
int fre0[33] = { 0 };
// Stores the count of set bits
int fre1[33] = { 0 };
// Traverse the array
for (int i = 0; i < n; i++) {
int x = arr[i];
// Traverse the bit of arr[i]
for (int j = 0; j < 33; j++) {
// If current bit is set
if (x & 1) {
// Increment fre1[j]
fre1[j] += 1;
}
// Otherwise
else {
// Increment fre0[j]
fre0[j] += 1;
}
// Right shift x by 1
x = x >> 1;
}
}
// Stores the count of total moves
int ans = 0;
// Traverse the range [0, 32]
for (int i = 0; i < 33; i++) {
// Update the value of ans
ans += min(fre0[i], fre1[i]);
}
// Return the minimum number of
// flips required
return ans;
}
// Driver Code
int main()
{
int arr[] = { 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << makeEqual(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to count minimum number
// of bits required to be flipped
// to make all array elements equal
static int makeEqual(int arr[], int n)
{
// Stores the count of unset bits
int fre0[] = new int[33];
// Stores the count of set bits
int fre1[] = new int[33];
// Traverse the array
for(int i = 0; i < n; i++)
{
int x = arr[i];
// Traverse the bit of arr[i]
for(int j = 0; j < 33; j++)
{
// If current bit is set
if ((x & 1) != 0)
{
// Increment fre1[j]
fre1[j] += 1;
}
// Otherwise
else
{
// Increment fre0[j]
fre0[j] += 1;
}
// Right shift x by 1
x = x >> 1;
}
}
// Stores the count of total moves
int ans = 0;
// Traverse the range [0, 32]
for(int i = 0; i < 33; i++)
{
// Update the value of ans
ans += Math.min(fre0[i], fre1[i]);
}
// Return the minimum number of
// flips required
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 5 };
int N = arr.length;
System.out.print(makeEqual(arr, N));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to count minimum number # of bits required to be flipped # to make all array elements equal def makeEqual(arr, n): # Stores the count of unset bits fre0 = [0]*33 # Stores the count of set bits fre1 = [0]*33 # Traverse the array for i in range(n): x = arr[i] # Traverse the bit of arr[i] for j in range(33): # If current bit is set if (x & 1): # Increment fre1[j] fre1[j] += 1 # Otherwise else: # Increment fre0[j] fre0[j] += 1 # Right shift x by 1 x = x >> 1 # Stores the count of total moves ans = 0 # Traverse the range [0, 32] for i in range(33): # Update the value of ans ans += min(fre0[i], fre1[i]) # Return the minimum number of # flips required return ans # Driver Code if __name__ == '__main__': arr= [3, 5] N = len(arr) print(makeEqual(arr, N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG {
// Function to count minimum number
// of bits required to be flipped
// to make all array elements equal
static int makeEqual(int[] arr, int n)
{
// Stores the count of unset bits
int[] fre0 = new int[33];
// Stores the count of set bits
int[] fre1 = new int[33];
// Traverse the array
for (int i = 0; i < n; i++) {
int x = arr[i];
// Traverse the bit of arr[i]
for (int j = 0; j < 33; j++) {
// If current bit is set
if ((x & 1) != 0) {
// Increment fre1[j]
fre1[j] += 1;
}
// Otherwise
else {
// Increment fre0[j]
fre0[j] += 1;
}
// Right shift x by 1
x = x >> 1;
}
}
// Stores the count of total moves
int ans = 0;
// Traverse the range [0, 32]
for (int i = 0; i < 33; i++) {
// Update the value of ans
ans += Math.Min(fre0[i], fre1[i]);
}
// Return the minimum number of
// flips required
return ans;
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 5 };
int N = arr.Length;
Console.WriteLine(makeEqual(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript program for the above approach
// Function to count minimum number
// of bits required to be flipped
// to make all array elements equal
function makeEqual(arr , n)
{
// Stores the count of unset bits
var fre0 = Array(33).fill(0);
// Stores the count of set bits
var fre1 = Array(33).fill(0);
// Traverse the array
for (i = 0; i < n; i++) {
var x = arr[i];
// Traverse the bit of arr[i]
for (j = 0; j < 33; j++) {
// If current bit is set
if ((x & 1) != 0) {
// Increment fre1[j]
fre1[j] += 1;
}
// Otherwise
else {
// Increment fre0[j]
fre0[j] += 1;
}
// Right shift x by 1
x = x >> 1;
}
}
// Stores the count of total moves
var ans = 0;
// Traverse the range [0, 32]
for (i = 0; i < 33; i++) {
// Update the value of ans
ans += Math.min(fre0[i], fre1[i]);
}
// Return the minimum number of
// flips required
return ans;
}
// Driver Code
var arr = [ 3, 5 ];
var N = arr.length;
document.write(makeEqual(arr, N));
// This code is contributed by aashish1995
</script>
Producción:
2
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA