Valor OR máximo de un par en una array

Dada una array arr[] de N elementos positivos. La tarea es encontrar el valor OR bit a bit máximo de un par de la array dada.
Ejemplos: 

Entrada: arr[] = {4, 8, 12, 16} 
Salida: 28 
(12, 16) es el par con el OR bit a bit máximo. 
12 | 16 = 28

Entrada: arr[] = {4, 8, 16, 2} 
Salida: 24 

Enfoque: iterar sobre todos los pares posibles y calcular el valor OR de estos pares. Finalmente, imprima el máximo de todos los valores.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum bitwise OR
// for any pair of the given array
int maxOR(int arr[], int n)
{
 
    // To store the maximum OR value
    int maxVal = 0;
 
    // For every possible pair
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++) {
 
            // Update the maximum OR value
            maxVal = max(maxVal, arr[i] | arr[j]);
        }
 
    return maxVal;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 8, 12, 16 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxOR(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    // Function to return the maximum bitwise OR
    // for any pair of the given array
    static int maxOR(int arr[], int n)
    {
 
        // To store the maximum OR value
        int maxVal = 0;
 
        // For every possible pair
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++) {
 
                // Update the maximum OR value
                maxVal = Math.max(maxVal, arr[i] | arr[j]);
            }
 
        return maxVal;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 4, 8, 12, 16 };
        int n = arr.length;
 
        System.out.println(maxOR(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the maximum bitwise OR
# for any pair of the given array
def maxOR(arr, n):
     
    # To store the maximum OR value
    maxVal = 0;
 
    # For every possible pair
    for i in range(n - 1):
        for j in range(i + 1, n):
             
            # Update the maximum OR value
            maxVal = max(maxVal, arr[i] | arr[j]);
 
    return maxVal;
 
# Driver code
if __name__ == '__main__':
    arr = [4, 8, 12, 16];
    n = len(arr);
 
    print(maxOR(arr, n));
 
# This code is contributed by 29AjayKumar

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to return the maximum bitwise OR
    // for any pair of the given array
    static int maxOR(int[] arr, int n)
    {
 
        // To store the maximum OR value
        int maxVal = 0;
 
        // For every possible pair
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++) {
 
                // Update the maximum OR value
                maxVal = Math.Max(maxVal, arr[i] | arr[j]);
            }
 
        return maxVal;
    }
 
    // Driver code
    static public void Main()
    {
        int[] arr = { 4, 8, 12, 16 };
        int n = arr.Length;
 
        Console.Write(maxOR(arr, n));
    }
}
 
// This code is contributed by ajit.

<script>
    // Javascript implementation of the approach
     
      // Function to return the maximum bitwise OR
    // for any pair of the given array
    function maxOR(arr, n)
    {
  
        // To store the maximum OR value
        let maxVal = 0;
  
        // For every possible pair
        for (let i = 0; i < n - 1; i++)
            for (let j = i + 1; j < n; j++) {
  
                // Update the maximum OR value
                maxVal = Math.max(maxVal, arr[i] | arr[j]);
            }
  
        return maxVal;
    }
     
    let arr = [ 4, 8, 12, 16 ];
    let n = arr.length;
 
    document.write(maxOR(arr, n));
</script>

28

Complejidad temporal: O(n*n)

Espacio Auxiliar: O(1)

Enfoque eficiente: en este problema, el enfoque efectivo sería encontrar el elemento que tiene el mayor número de pares en la array. Tenemos los siguientes pasos para este enfoque:

• Primero encuentre el número más alto en la array y asígnele el nombre max_value.
• itere sobre la array y verifique uno por uno el máximo de bit a bit o de max_value con todos los números de la array.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach ( Linear time Complexity )
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum bitwise OR
// for any pair of the given array
// in O(n) time complexity.
int maxOR(int arr[], int n)
{
    // find maximum element in the array
    int max_value = *max_element(arr, arr + n);
 
    // To store the maximum OR value
    int ans = 0;
 
    // iterate over rest array elements and find maximum OR value pair
    for (int i = 0; i < n; i++) {
        ans = max(ans, (max_value | arr[i]));
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 6, 8, 16 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxOR(arr, n);
 
    return 0;
}

// Java implementation of the approach
// (Linear time Complexity)
import java.util.Arrays;
 
class GFG{
     
// Function to return the maximum bitwise
// OR for any pair of the given array
// in O(n) time complexity.
public static int maxOR(int[] arr, int n)
{
     
    // Find maximum element in the array
    int max_value = Arrays.stream(arr).max().getAsInt();
     
    // To store the maximum OR value
    int ans = 0;
   
    // Iterate over rest array elements and
    // find maximum OR value pair
    for(int i = 0; i < n; i++)
    {
        ans = Math.max(ans, (max_value | arr[i]));
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 6, 8, 16 };
    int n = arr.length;
     
    System.out.print(maxOR(arr, n));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 implementation of the approach
# (Linear time Complexity)
  
# Function to return the maximum bitwise
# OR for any pair of the given array
def maxOR(arr, n):
      
    # To store the maximum element
    # of the array
    maxVal = max(arr)
     
    # To store the maximum OR value
    ans = 0
     
    # Iterate over rest array elements and
    # find maximum OR value pair
    for i in range(n - 1):
         
        # Update the maximum OR value
        ans = max(ans, maxVal | arr[i])
   
    return ans
   
# Driver code
if __name__ == '__main__':
     
    arr = [ 3, 6, 8, 16 ]
    n = len(arr)
     
    print(maxOR(arr, n))
     
# This code is contributed by math_lover

// C# implementation of the approach
// (Linear time Complexity)
using System;
using System.Linq;
 
class GFG{
     
// Function to return the maximum bitwise
// OR for any pair of the given array
// in O(n) time complexity.
static int maxOR(int []arr, int n)
{
     
    // Find maximum element in the array
    int max_value = arr.Max();
 
    // To store the maximum OR value
    int ans = 0;
 
    // Iterate over rest array elements and
    // find maximum OR value pair
    for(int i = 0; i < n; i++)
    {
        ans = Math.Max(ans, (max_value | arr[i]));
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 6, 8, 16 };
    int n = arr.Length;
 
    Console.Write(maxOR(arr, n));
}
}
 
// This code is contributed by doreamon_

<script>
    // Javascript implementation of the approach
    // (Linear time Complexity)
     
    // Function to return the maximum bitwise
    // OR for any pair of the given array
    // in O(n) time complexity.
    function maxOR(arr, n)
    {
 
        // Find maximum element in the array
        let max_value = Number.MIN_VALUE;
        for(let i = 0; i < n; i++)
        {
            max_value = Math.max(max_value, arr[i]);
        }
 
        // To store the maximum OR value
        let ans = 0;
 
        // Iterate over rest array elements and
        // find maximum OR value pair
        for(let i = 0; i < n; i++)
        {
            ans = Math.max(ans, (max_value | arr[i]));
        }
        return ans;
    }
     
    let arr = [ 3, 6, 8, 16 ];
    let n = arr.length;
  
    document.write(maxOR(arr, n));
     
</script>

Producción:

24

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)