Dados dos arreglos arr[] y brr[] de longitud N y M respectivamente, cree un arreglo res[] de largo N usando las siguientes operaciones de modo que el OR bit a bit de todos los elementos en el arreglo res[] sea mínimo.
- Para cada índice i en arr[] , elija cualquier índice j ( repeticiones permitidas ) de la array brr[] y actualice res[i] = arr[i] & brr[j]
La tarea es imprimir el valor del mínimo posible Bitwise OR de los elementos de la array res[] .
Ejemplos:
Entrada: arr[] = {2, 1}, brr[] = {4, 6, 7}
Salida: 0
Explicación:
Para la array arr[] = {2, 1}, elija los valores de brr[] como { 4, 4} o {4, 6}.
Por lo tanto, la array resultante se convierte en {0, 0} y el OR bit a bit de la array resultante = 0, que es el valor mínimo posible.Entrada: arr[] = {1, 2, 3}, brr[] = {7, 15}
Salida: 3
Explicación:
Para la array arr[] = {1, 2, 3}, elija los valores de brr[] como {7, 7, 7}.
Por lo tanto, la array resultante se convierte en {1, 2, 3} y el OR bit a bit de la array resultante = 3.
Enfoque ingenuo: el enfoque más simple es generar Bitwise OR de todos los pares posibles de las arrays arr[] con brr[] . Después de completar los pasos anteriores, elija solo aquellos N elementos cuyo Bitwise OR sea mínimo. Imprime ese mínimo Bitwise OR.
Complejidad de Tiempo: O(2 (N * M) )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es comenzar con la máxima respuesta posible y luego tratar de minimizarla en cada paso. A continuación se muestran los pasos:
- Inicialice la respuesta máxima posible (por ejemplo, ans ), que será un número en el que se establecen todos los bits .
- Recorra cada bit de 31 a 0 y verifique si ese bit se puede desactivar o no, ya que hacer que un bit en particular sea 0 minimizará la respuesta general.
- Para cada bit no establecido en los pasos anteriores, verifique si todos los elementos de la array resultante darán el OR bit a bit como la posible respuesta actual o no. Si se determina que es cierto, actualice la respuesta actual con la respuesta mínima.
- Después de completar los pasos anteriores, imprima el valor del valor mínimo posible de Bitwise almacenado en ans.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to check if it is possible
// to make current no as minimum result
// using array a and b
bool check(ll no, vector<int>& a,
vector<int>& b)
{
int count = 0;
// Size of the first array
int n = a.size();
// Size of the second array
int m = b.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
// Check for the number as
// ans is possible or not
if (((a[i] & b[j]) | no) == no) {
count++;
break;
}
}
}
// If all the elements of array
// gives no as the Bitwise OR
if (count == n)
return true;
else
return false;
}
// Function to find the minimum bitwise
// OR of all the element in res[]
ll findMinValue(vector<int>& a,
vector<int>& b)
{
// Max possible ans
ll ans = (1LL << 31) - 1;
for (ll i = 30; i >= 0; --i) {
// Check for the upper bit that
// can be make off or not
if (check(ans ^ (1 << i), a, b)) {
ans = ans ^ (1 << i);
}
}
return ans;
}
// Driver Code
int main()
{
// Given array a[] and b[]
vector<int> a = { 1, 2, 3 };
vector<int> b = { 7, 15 };
// Function Call
cout << findMinValue(a, b);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
// Function to check if it is possible
// to make current no as minimum result
// using array a and b
static boolean check(int no,
int []a, int []b)
{
int count = 0;
// Size of the first array
int n = a.length;
// Size of the second array
int m = b.length;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
// Check for the number as
// ans is possible or not
if (((a[i] & b[j]) | no) == no)
{
count++;
break;
}
}
}
// If all the elements of array
// gives no as the Bitwise OR
if (count == n)
return true;
else
return false;
}
// Function to find the minimum
// bitwise OR of all the
// element in res[]
static int findMinValue(int []a,
int []b)
{
// Max possible ans
int ans = (1 << 31) - 1;
for (int i = 30; i >= 0; --i)
{
// Check for the upper bit that
// can be make off or not
if (check(ans ^ (1 << i), a, b))
{
ans = ans ^ (1 << i);
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array a[] and b[]
int []a = {1, 2, 3};
int []b = {7, 15};
// Function Call
System.out.print(findMinValue(a, b));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to check if it is possible # to make current no as minimum result # using array a and b def check(no, a, b): count = 0 # Size of the first array n = len(a) # Size of the second array m = len(b) for i in range(n): for j in range(m): # Check for the number as # ans is possible or not if (((a[i] & b[j]) | no) == no): count += 1 break # If athe elements of array # gives no as the Bitwise OR if (count == n): return True else: return False # Function to find the minimum bitwise # OR of athe element in res[] def findMinValue(a, b): # Max possible ans ans = (1 << 31) - 1 for i in range(30, -1, -1): # Check for the upper bit that # can be make off or not if (check(ans ^ (1 << i), a, b)): ans = ans ^ (1 << i) return ans # Driver Code if __name__ == '__main__': # Given array a[] and b[] a = [ 1, 2, 3 ] b = [ 7, 15 ] # Function call print(findMinValue(a, b)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if it is possible
// to make current no as minimum result
// using array a and b
static bool check(int no, int []a,
int []b)
{
int count = 0;
// Size of the first array
int n = a.Length;
// Size of the second array
int m = b.Length;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
// Check for the number as
// ans is possible or not
if (((a[i] & b[j]) | no) == no)
{
count++;
break;
}
}
}
// If all the elements of array
// gives no as the Bitwise OR
if (count == n)
return true;
else
return false;
}
// Function to find the minimum
// bitwise OR of all the
// element in res[]
static int findMinValue(int []a,
int []b)
{
// Max possible ans
int ans = int.MaxValue;
for(int i = 30; i >= 0; --i)
{
// Check for the upper bit that
// can be make off or not
if (check(ans ^ (1 << i), a, b))
{
ans = ans ^ (1 << i);
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []a and []b
int []a = { 1, 2, 3 };
int []b = { 7, 15 };
// Function call
Console.Write(findMinValue(a, b));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if it is possible
// to make current no as minimum result
// using array a and b
function check(no,
a, b)
{
let count = 0;
// Size of the first array
let n = a.length;
// Size of the second array
let m = b.length;
for (let i = 0; i < n; ++i)
{
for (let j = 0; j < m; ++j)
{
// Check for the number as
// ans is possible or not
if (((a[i] & b[j]) | no) == no)
{
count++;
break;
}
}
}
// If all the elements of array
// gives no as the Bitwise OR
if (count == n)
return true;
else
return false;
}
// Function to find the minimum
// bitwise OR of all the
// element in res[]
function findMinValue(a,b)
{
// Max possible ans
let ans = (1 << 31) - 1;
for (let i = 30; i >= 0; --i)
{
// Check for the upper bit that
// can be make off or not
if (check(ans ^ (1 << i), a, b))
{
ans = ans ^ (1 << i);
}
}
return ans;
}
// Driver code
// Given array a[] and b[]
let a = [1, 2, 3];
let b = [7, 15];
// Function Call
document.write(findMinValue(a, b));
// This code is contributed by target_2.
</script>
Producción:
3
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)