Dada una array a de tamaño N y un número entero K . La tarea es encontrar el máximo bit a bit y el valor de los elementos de cualquier subsecuencia de longitud K .
Nota : a[i] <= 10 9
Ejemplos:
Entrada: a[] = {10, 20, 15, 4, 14}, K = 4
Salida: 4
{20, 15, 4, 14} es la subsecuencia con el valor ‘&’ más alto.
Entrada: a[] = {255, 127, 31, 5, 24, 37, 15}, K = 5
Salida: 8
Enfoque ingenuo : un enfoque ingenuo es encontrar recursivamente el bit a bit y el valor de todas las subsecuencias de longitud K y el máximo entre todos ellos será la respuesta.
Enfoque eficiente : un enfoque eficiente es resolverlo usando propiedades de bits . A continuación se muestran los pasos para resolver el problema:
- Iterar desde la izquierda (inicialmente izquierda = 31 como 2 32 > 10 9 ) hasta que encontremos > K números en el vector temp (inicialmente temp = arr ) cuyo i-ésimo bit está configurado. Actualice el nuevo conjunto de números a la array temporal
- Si no obtenemos > K números, el valor & de cualquier elemento K en la array temporal será el valor & máximo posible.
- Repita el paso 1 con la izquierda reiniciada como primer bit + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of
// the addition of all possible subsets.
#include <bits/stdc++.h>
using namespace std;
// Function to perform step-1
vector<int> findSubset(vector<int>& temp, int& last, int k)
{
vector<int> ans;
// Iterate from left till 0
// till we get a bit set of K numbers
for (int i = last; i >= 0; i--) {
int cnt = 0;
// Count the numbers whose
// i-th bit is set
for (auto it : temp) {
int bit = it & (1 << i);
if (bit > 0)
cnt++;
}
// If the array has numbers>=k
// whose i-th bit is set
if (cnt >= k) {
for (auto it : temp) {
int bit = it & (1 << i);
if (bit > 0)
ans.push_back(it);
}
// Update last
last = i - 1;
// Return the new set of numbers
return ans;
}
}
return ans;
}
// Function to find the maximum '&' value
// of K elements in subsequence
int findMaxiumAnd(int a[], int n, int k)
{
int last = 31;
// Temporary arrays
vector<int> temp1, temp2;
// Initially temp = arr
for (int i = 0; i < n; i++) {
temp2.push_back(a[i]);
}
// Iterate till we have >=K elements
while ((int)temp2.size() >= k) {
// Temp array
temp1 = temp2;
// Find new temp array if
// K elements are there
temp2 = findSubset(temp2, last, k);
}
// Find the & value
int ans = temp1[0];
for (int i = 0; i < k; i++)
ans = ans & temp1[i];
return ans;
}
// Driver Code
int main()
{
int a[] = { 255, 127, 31, 5, 24, 37, 15 };
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout << findMaxiumAnd(a, n, k);
}
Java
// Java program to find the sum of
// the addition of all possible subsets.
import java.util.*;
class GFG
{
static int last;
// Function to perform step-1
static Vector<Integer>
findSubset(Vector<Integer> temp, int k)
{
Vector<Integer> ans = new Vector<Integer>();
// Iterate from left till 0
// till we get a bit set of K numbers
for (int i = last; i >= 0; i--)
{
int cnt = 0;
// Count the numbers whose
// i-th bit is set
for (Integer it : temp)
{
int bit = it & (1 << i);
if (bit > 0)
cnt++;
}
// If the array has numbers>=k
// whose i-th bit is set
if (cnt >= k)
{
for (Integer it : temp)
{
int bit = it & (1 << i);
if (bit > 0)
ans.add(it);
}
// Update last
last = i - 1;
// Return the new set of numbers
return ans;
}
}
return ans;
}
// Function to find the maximum '&' value
// of K elements in subsequence
static int findMaxiumAnd(int a[], int n, int k)
{
last = 31;
// Temporary arrays
Vector<Integer> temp1 = new Vector<Integer>();
Vector<Integer> temp2 = new Vector<Integer>();;
// Initially temp = arr
for (int i = 0; i < n; i++)
{
temp2.add(a[i]);
}
// Iterate till we have >=K elements
while ((int)temp2.size() >= k)
{
// Temp array
temp1 = temp2;
// Find new temp array if
// K elements are there
temp2 = findSubset(temp2, k);
}
// Find the & value
int ans = temp1.get(0);
for (int i = 0; i < k; i++)
ans = ans & temp1.get(i);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 255, 127, 31, 5, 24, 37, 15 };
int n = a.length;
int k = 4;
System.out.println(findMaxiumAnd(a, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the sum of # the addition of all possible subsets. last = 31 # Function to perform step-1 def findSubset(temp, k): global last ans = [] # Iterate from left till 0 # till we get a bit set of K numbers for i in range(last, -1, -1): cnt = 0 # Count the numbers whose # i-th bit is set for it in temp: bit = it & (1 << i) if (bit > 0): cnt += 1 # If the array has numbers>=k # whose i-th bit is set if (cnt >= k): for it in temp: bit = it & (1 << i) if (bit > 0): ans.append(it) # Update last last = i - 1 # Return the new set of numbers return ans return ans # Function to find the maximum '&' value # of K elements in subsequence def findMaxiumAnd(a, n, k): global last # Temporary arrays temp1, temp2, = [], [] # Initially temp = arr for i in range(n): temp2.append(a[i]) # Iterate till we have >=K elements while len(temp2) >= k: # Temp array temp1 = temp2 # Find new temp array if # K elements are there temp2 = findSubset(temp2, k) # Find the & value ans = temp1[0] for i in range(k): ans = ans & temp1[i] return ans # Driver Code a = [255, 127, 31, 5, 24, 37, 15] n = len(a) k = 4 print(findMaxiumAnd(a, n, k)) # This code is contributed by Mohit Kumar
C#
// C# program to find the sum of
// the addition of all possible subsets.
using System;
using System.Collections.Generic;
class GFG
{
static int last;
// Function to perform step-1
static List<int>findSubset(List<int> temp, int k)
{
List<int> ans = new List<int>();
// Iterate from left till 0
// till we get a bit set of K numbers
for (int i = last; i >= 0; i--)
{
int cnt = 0;
// Count the numbers whose
// i-th bit is set
foreach (int it in temp)
{
int bit = it & (1 << i);
if (bit > 0)
cnt++;
}
// If the array has numbers>=k
// whose i-th bit is set
if (cnt >= k)
{
foreach (int it in temp)
{
int bit = it & (1 << i);
if (bit > 0)
ans.Add(it);
}
// Update last
last = i - 1;
// Return the new set of numbers
return ans;
}
}
return ans;
}
// Function to find the maximum '&' value
// of K elements in subsequence
static int findMaxiumAnd(int []a, int n, int k)
{
last = 31;
// Temporary arrays
List<int> temp1 = new List<int>();
List<int> temp2 = new List<int>();;
// Initially temp = arr
for (int i = 0; i < n; i++)
{
temp2.Add(a[i]);
}
// Iterate till we have >=K elements
while ((int)temp2.Count >= k)
{
// Temp array
temp1 = temp2;
// Find new temp array if
// K elements are there
temp2 = findSubset(temp2, k);
}
// Find the & value
int ans = temp1[0];
for (int i = 0; i < k; i++)
ans = ans & temp1[i];
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 255, 127, 31, 5, 24, 37, 15 };
int n = a.Length;
int k = 4;
Console.WriteLine(findMaxiumAnd(a, n, k));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the sum of
// the addition of all possible subsets.
// Function to perform step-1
function findSubset(temp,k)
{
let ans = [];
// Iterate from left till 0
// till we get a bit set of K numbers
for (let i = last; i >= 0; i--)
{
let cnt = 0;
// Count the numbers whose
// i-th bit is set
for (let it=0;it< temp.length;it++)
{
let bit = temp[it] & (1 << i);
if (bit > 0)
cnt++;
}
// If the array has numbers>=k
// whose i-th bit is set
if (cnt >= k)
{
for (let it=0;it< temp.length;it++)
{
let bit = temp[it] & (1 << i);
if (bit > 0)
ans.push(temp[it]);
}
// Update last
last = i - 1;
// Return the new set of numbers
return ans;
}
}
return ans;
}
// Function to find the maximum '&' value
// of K elements in subsequence
function findMaxiumAnd(a,n,k)
{
last = 31;
// Temporary arrays
let temp1 = [];
let temp2 = [];
// Initially temp = arr
for (let i = 0; i < n; i++)
{
temp2.push(a[i]);
}
// Iterate till we have >=K elements
while (temp2.length >= k)
{
// Temp array
temp1 = temp2;
// Find new temp array if
// K elements are there
temp2 = findSubset(temp2, k);
}
// Find the & value
let ans = temp1[0];
for (let i = 0; i < k; i++)
ans = ans & temp1[i];
return ans;
}
// Driver Code
let a=[255, 127, 31, 5, 24, 37, 15 ];
let n = a.length;
let k = 4;
document.write(findMaxiumAnd(a, n, k));
// This code is contributed by unknown2108
</script>
Producción:
24
Complejidad de tiempo: O (N * N), ya que estamos usando un bucle para atravesar N veces y en cada recorrido estamos llamando a la función findSubset que costará O (N) tiempo. Donde N es el número de elementos de la array.
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para la array temporal. Donde N es el número de elementos de la array.