Dada una array arr[] de N elementos, la tarea es eliminar un elemento de la array de modo que el valor OR de la array se minimice. Imprime el valor minimizado.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 3
Todas las formas posibles de eliminar un elemento y sus
valores OR correspondientes serán:
a) Eliminar 1 -> (2 | 3) = 3
b) Eliminar 2 -> (1 | 3) = 3
c) Eliminar 3 -> (1 | 2) = 3
Por lo tanto, la respuesta será 3.
Entrada: arr[] = {2, 2, 2}
Salida: 2
Enfoque ingenuo: una forma será eliminar cada elemento uno por uno y luego encontrar el OR de los elementos restantes. La complejidad temporal de este enfoque será O(N 2 ).
Enfoque eficiente: para resolver el problema de manera eficiente, se debe determinar el valor de (OR(arr[0…i-1]) | OR(arr[i+1…N-1])) para cualquier elemento arr[i] . Para hacerlo, las arrays OR de prefijo y sufijo se pueden calcular, por ejemplo, pre[] y suf[] donde pre[i] almacena OR(arr[0…i]) y suff[i] almacena OR(arr[i…N -1]) . Luego, el valor OR de la array después de eliminar el i -ésimo elemento se puede calcular como (pre[i-1] | suff[i+1]) y la respuesta será el mínimo de todos los valores OR posibles.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimized OR
// after removing an element from the array
int minOR(int* arr, int n)
{
// Base case
if (n == 1)
return 0;
// Prefix and suffix OR array
int pre[n], suf[n];
pre[0] = arr[0], suf[n - 1] = arr[n - 1];
// Computing prefix/suffix OR arrays
for (int i = 1; i < n; i++)
pre[i] = (pre[i - 1] | arr[i]);
for (int i = n - 2; i >= 0; i--)
suf[i] = (suf[i + 1] | arr[i]);
// To store the final answer
int ans = min(pre[n - 2], suf[1]);
// Finding the final answer
for (int i = 1; i < n - 1; i++)
ans = min(ans, (pre[i - 1] | suf[i + 1]));
// Returning the final answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr) / sizeof(int);
cout << minOR(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimized OR
// after removing an element from the array
static int minOR(int []arr, int n)
{
// Base case
if (n == 1)
return 0;
// Prefix and suffix OR array
int []pre = new int[n];
int []suf = new int[n];
pre[0] = arr[0];
suf[n - 1] = arr[n - 1];
// Computing prefix/suffix OR arrays
for (int i = 1; i < n; i++)
pre[i] = (pre[i - 1] | arr[i]);
for (int i = n - 2; i >= 0; i--)
suf[i] = (suf[i + 1] | arr[i]);
// To store the final answer
int ans = Math.min(pre[n - 2], suf[1]);
// Finding the final answer
for (int i = 1; i < n - 1; i++)
ans = Math.min(ans, (pre[i - 1] |
suf[i + 1]));
// Returning the final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int n = arr.length;
System.out.print(minOR(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the minimized OR # after removing an element from the array def minOR(arr, n): # Base case if (n == 1): return 0 # Prefix and suffix OR array pre = [0] * n suf = [0] * n pre[0] = arr[0] suf[n - 1] = arr[n - 1] # Computing prefix/suffix OR arrays for i in range(1, n): pre[i] = (pre[i - 1] | arr[i]) for i in range(n - 2, -1, -1): suf[i] = (suf[i + 1] | arr[i]) # To store the final answer ans = min(pre[n - 2], suf[1]) # Finding the final answer for i in range(1, n - 1): ans = min(ans, (pre[i - 1] | suf[i + 1])) # Returning the final answer return ans # Driver code if __name__ == '__main__': arr = [1, 2, 3] n = len(arr) print(minOR(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimized OR
// after removing an element from the array
static int minOR(int []arr, int n)
{
// Base case
if (n == 1)
return 0;
// Prefix and suffix OR array
int []pre = new int[n];
int []suf = new int[n];
pre[0] = arr[0];
suf[n - 1] = arr[n - 1];
// Computing prefix/suffix OR arrays
for (int i = 1; i < n; i++)
pre[i] = (pre[i - 1] | arr[i]);
for (int i = n - 2; i >= 0; i--)
suf[i] = (suf[i + 1] | arr[i]);
// To store the final answer
int ans = Math.Min(pre[n - 2], suf[1]);
// Finding the final answer
for (int i = 1; i < n - 1; i++)
ans = Math.Min(ans, (pre[i - 1] |
suf[i + 1]));
// Returning the final answer
return ans;
}
// Driver code
static public void Main ()
{
int []arr = { 1, 2, 3 };
int n = arr.Length;
Console.WriteLine(minOR(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimized OR
// after removing an element from the array
function minOR(arr, n)
{
// Base case
if (n == 1)
return 0;
// Prefix and suffix OR array
var pre = Array(n), suf = Array(n);
pre[0] = arr[0], suf[n - 1] = arr[n - 1];
// Computing prefix/suffix OR arrays
for (var i = 1; i < n; i++)
pre[i] = (pre[i - 1] | arr[i]);
for (var i = n - 2; i >= 0; i--)
suf[i] = (suf[i + 1] | arr[i]);
// To store the final answer
var ans = Math.min(pre[n - 2], suf[1]);
// Finding the final answer
for (var i = 1; i < n - 1; i++)
ans = Math.min(ans, (pre[i - 1] | suf[i + 1]));
// Returning the final answer
return ans;
}
// Driver code
var arr = [1, 2, 3];
var n = arr.length;
document.write( minOR(arr, n));
</script>
3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA