Mínimo posible Bitwise OR de todos Bitwise AND de pares generados a partir de dos arrays dadas

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:
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:
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:

  1. Inicialice la respuesta máxima posible (por ejemplo, ans ), que será un número en el que se establecen todos los bits .
  2. 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.
  3. 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.
  4. 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)

Publicación traducida automáticamente

Artículo escrito por dreamer07 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 *