Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar el entero X más pequeño con exactamente K bits establecidos de tal manera que la suma de Bitwise AND de X con cada elemento de la array arr[i] sea máxima.
Ejemplos:
Entrada: arr[] = {3, 4, 5, 1}, K = 1
Salida: 4
Explicación: Considere el valor de X como 4. Luego, la suma de Bitwise AND de X y los elementos de la array = 4 & 3 + 4 & 4 + 4 & 5 + 4 & 1 = 0 + 4 + 4 + 0 = 8, que es el máximo.Entrada: arr[] = {1, 3, 4, 5, 2, 5}, K = 2
Salida: 5
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos X como 0 , para almacenar el valor resultante de X.
- Inicialice una array, digamos count[] de tamaño 30 , para almacenar en cada i -ésimo índice, los elementos de la array de números que tienen el i -ésimo bit establecido .
- Recorra la array dada y si el i -ésimo bit está establecido , actualice count[i] en 1 .
- Inicialice un vector de pares , digamos ans , para almacenar la contribución de cada bit y valores, es decir, si se establece el I -th bit, luego almacene el valor {i, count[i]2 i } en Ans .
- Ordena el vector de pares en orden descendente de los segundos elementos .
- Recorra el vector Ans sobre el rango [0, K – 1] y actualice el valor de X como el OR bit a bit de X y 2 (Ans[i].first) .
- Después de completar los pasos anteriores, imprima el valor de X como resultado.
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;
// Comparator function to sort the
// vector of pairs
bool comp(pair<int, int>& a,
pair<int, int>& b)
{
// If the second is not the same
// then sort in decreasing order
if (a.second != b.second)
return a.second > b.second;
// Otherwise
return a.first < b.first;
}
// Function to find the value of X
// such that Bitwise AND of all array
// elements with X is maximum
int maximizeSum(int arr[], int n, int k)
{
// Stores the count of set bit at
// each position
vector<int> cnt(30, 0);
// Stores the resultant value of X
int X = 0;
// Calculate the count of set bits
// at each position
for (int i = 0; i < n; i++) {
for (int j = 0; j < 30; j++) {
// If the jth bit is set
if (arr[i] & (1 << j))
cnt[j]++;
}
}
// Stores the contribution
// of each set bit
vector<pair<int, int> > v;
// Store all bit and amount of
// contribution
for (int i = 0; i < 30; i++) {
// Find the total contribution
int gain = cnt[i] * (1 << i);
v.push_back({ i, gain });
}
// Sort V[] in decreasing
// order of second parameter
sort(v.begin(), v.end(), comp);
// Choose exactly K set bits
for (int i = 0; i < k; i++) {
X |= (1 << v[i].first);
}
// Print the answer
cout << X;
}
// Driver Code
int main()
{
int arr[] = { 3, 4, 5, 1 };
int K = 1;
int N = sizeof(arr) / sizeof(arr[0]);
maximizeSum(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the value of X
// such that Bitwise AND of all array
// elements with X is maximum
static void maximizeSum(int arr[], int n, int k)
{
// Stores the count of set bit at
// each position
int cnt[] = new int[30];
// Stores the resultant value of X
int X = 0;
// Calculate the count of set bits
// at each position
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 30; j++)
{
// If the jth bit is set
if ((arr[i] & (1 << j)) != 0)
cnt[j]++;
}
}
// Stores the contribution
// of each set bit
ArrayList<int[]> v = new ArrayList<>();
// Store all bit and amount of
// contribution
for(int i = 0; i < 30; i++)
{
// Find the total contribution
int gain = cnt[i] * (1 << i);
v.add(new int[] { i, gain });
}
// Sort V[] in decreasing
// order of second parameter
Collections.sort(v, (a, b) -> {
// If the second is not the same
// then sort in decreasing order
if (a[1] != b[1])
return b[1] - a[1];
// Otherwise
return a[0] - b[0];
});
// Choose exactly K set bits
for(int i = 0; i < k; i++)
{
X |= (1 << v.get(i)[0]);
}
// Print the answer
System.out.println(X);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 4, 5, 1 };
int K = 1;
int N = arr.length;
maximizeSum(arr, N, K);
}
}
// This code is contributed by Kingash
Javascript
<script>
// JavaScript program for the above approach
// Function to find the value of X
// such that Bitwise AND of all array
// elements with X is maximum
function maximizeSum(arr, n, k) {
// Stores the count of set bit at
// each position
let cnt = new Array(30).fill(0);
// Stores the resultant value of X
let X = 0;
// Calculate the count of set bits
// at each position
for (let i = 0; i < n; i++) {
for (let j = 0; j < 30; j++) {
// If the jth bit is set
if (arr[i] & (1 << j))
cnt[j]++;
}
}
// Stores the contribution
// of each set bit
let v = new Array();
// Store all bit and amount of
// contribution
for (let i = 0; i < 30; i++) {
// Find the total contribution
let gain = cnt[i] * (1 << i);
v.push([i, gain]);
}
// Sort V[] in decreasing
// order of second parameter
v.sort((a, b) => {
// If the second is not the same
// then sort in decreasing order
if (a[1] != b[1])
return b[1] - a[1];
// Otherwise
return a[0] - b[0];
});
// Choose exactly K set bits
for (let i = 0; i < k; i++) {
X |= (1 << v[i][0]);
}
// Print the answer
document.write(X);
}
// Driver Code
let arr = [3, 4, 5, 1];
let K = 1;
let N = arr.length;
maximizeSum(arr, N, K);
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA