Valor OR máximo de un par en un Array sin usar el operador OR

Dada una array arr[] que contiene N enteros positivos, la tarea es encontrar el valor OR bit a bit máximo de un par en la array dada sin usar el operador OR bit a bit.
Ejemplos:

Entrada: arr[] = {3, 6, 8, 16} 
Salida: 24 
Explicación: 
El par que da el valor OR máximo es (8, 16) => 8|16 = 24
Entrada: arr[] = {8, 7, 3, 12} 
Salida: 15 
Explicación: 
Hay más de un par que nos da el valor OR máximo. Uno entre ellos => 8|7 = 15

Enfoque: la idea es encontrar los dos números que tienen la mayor cantidad de bits establecidos en índices distintos. De esta forma, el número resultante tendrá todos esos índices como un bit establecido, y esto se puede hacer sin usar el operador OR . 

• Averigüe el elemento máximo en la array y luego busque el elemento particular en la array restante que tendrá el bit establecido en los índices donde el elemento máximo tiene un bit no establecido.
• Para maximizar nuestra salida, tenemos que encontrar un elemento que tenga un bit establecido de tal manera que maximice nuestra salida.
• Calcule el complemento del elemento máximo en la array y encuentre el valor AND máximo con los otros números.
• El valor AND máximo de este complemento con otros elementos de la array nos dará la cantidad máxima de bits no establecidos que podrían establecerse en nuestra respuesta debido a otros elementos de la array.
• Agregar elementos máximos con este valor AND máximo nos dará nuestro par de valor OR máximo deseado sin usar la operación OR.

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
// without using bitwise OR operation
int maxOR(int arr[], int n)
{
 
    // find maximum element in the array
    int max_value
        = *max_element(arr, arr + n);
 
    int number_of_bits
        = floor(log2(max_value)) + 1;
 
    // finding complement will set
    // all unset bits in a number
    int complement
        = ((1 << number_of_bits) - 1)
          ^ max_value;
 
    int c = 0;
 
    // iterate through all other
    // array elements to find
    // maximum AND value
    for (int i = 0; i < n; i++) {
        if (arr[i] != max_value) {
            c = max(c, (complement & arr[i]));
        }
    }
 
    // c will give the maximum value
    // that could be added to max_value
    // to produce maximum OR value
    return (max_value + c);
}
 
// 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
import java.util.*;
class GFG{
 
// Function to return the maximum
// bitwise OR for any pair of the
// given array without using bitwise
// OR operation
static int maxOR(int arr[], int n)
{
 
    // find maximum element in the array
    int max_value =
        Arrays.stream(arr).max().getAsInt();
 
    int number_of_bits =
        (int)((Math.log(max_value))) + 2;
 
    // finding complement will set
    // all unset bits in a number
    int complement = ((1 << number_of_bits) - 1) ^
                       max_value;
 
    int c = 0;
 
    // iterate through all other
    // array elements to find
    // maximum AND value
    for (int i = 0; i < n; i++)
    {
        if (arr[i] != max_value)
        {
            c = Math.max(c,
                         (complement & arr[i]));
        }
    }
 
    // c will give the maximum value
    // that could be added to max_value
    // to produce maximum OR value
    return (max_value + c);
}
 
// 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 gauravrajput1

# Python3 implementation of the approach
from math import log2, floor
 
# Function to return the maximum bitwise OR
# for any pair of the given array
# without using bitwise OR operation
def maxOR(arr, n):
     
    # Find maximum element in the array
    max_value = max(arr)
 
    number_of_bits = floor(log2(max_value)) + 1
 
    # Finding complement will set
    # all unset bits in a number
    complement = (((1 << number_of_bits) - 1) ^
                 max_value)
    c = 0
 
    # Iterate through all other
    # array elements to find
    # maximum AND value
    for i in range(n):
         
        if (arr[i] != max_value):
            c = max(c, (complement & arr[i]))
 
    # c will give the maximum value
    # that could be added to max_value
    # to produce maximum OR value
    return (max_value + c)
 
# Driver code
if __name__ == '__main__':
     
    arr = [3, 6, 8, 16]
    n = len(arr)
 
    print(maxOR(arr, n))
 
# This code is contributed by Bhupendra_Singh

// C# program for the above approach
using System;
using System.Linq;
 
class GFG{
 
// Function to return the maximum
// bitwise OR for any pair of the
// given array without using bitwise
// OR operation
static int maxOR(int[] arr, int n)
{
 
    // Find maximum element in the array
    int max_value = arr.Max();
 
    int number_of_bits = (int)(Math.Log(max_value)) + 2;
 
    // Finding complement will set
    // all unset bits in a number
    int complement = ((1 << number_of_bits) - 1) ^
                      max_value;
 
    int c = 0;
 
    // Iterate through all other
    // array elements to find
    // maximum AND value
    for(int i = 0; i < n; i++)
    {
        if (arr[i] != max_value)
        {
            c = Math.Max(c,
                        (complement & arr[i]));
        }
    }
 
    // c will give the maximum value
    // that could be added to max_value
    // to produce maximum OR value
    return (max_value + c);
}
 
// Driver code
public static void Main()
{
    int[] arr = { 3, 6, 8, 16 };
    int n = arr.Length;
     
    Console.Write(maxOR(arr, n));
}
}
 
// This code is contributed by code_hunt

<script>
// javascript implementation
// of the approach
 
    // Function to return the maximum
    // bitwise OR for any pair of the
    // given array without using bitwise
    // OR operation
    function maxOR(arr , n) {
 
        // find maximum element in the array
        var max_value = Math.max.apply(Math,arr);
 
        var number_of_bits = parseInt( ((Math.log(max_value)))) + 2;
 
        // finding complement will set
        // all unset bits in a number
        var complement = ((1 << number_of_bits) - 1) ^ max_value;
 
        var c = 0;
 
        // iterate through all other
        // array elements to find
        // maximum AND value
        for (i = 0; i < n; i++) {
            if (arr[i] != max_value) {
                c = Math.max(c, (complement & arr[i]));
            }
        }
 
        // c will give the maximum value
        // that could be added to max_value
        // to produce maximum OR value
        return (max_value + c);
    }
 
    // Driver code
     
        var arr = [ 3, 6, 8, 16 ];
        var n = arr.length;
        document.write(maxOR(arr, n));
 
// This code is contributed by todaysgaurav
</script>

24

Complejidad de tiempo: O(N) 

Espacio Auxiliar: O(1)