OR máximo de dos números en una array

Dada una array Arr de enteros no negativos de tamaño N , la tarea es encontrar el máximo OR posible entre dos números presentes en la array.

Ejemplo:

Entrada: Arr = {25, 10, 2, 8, 5, 3}
Salida: 29

Entrada: Arr = {1, 2, 3, 4, 5, 6, 7}
Salida: 7

Enfoque ingenuo:

Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)

Mejor enfoque: el enfoque se basa en la siguiente observación bit a bit:

• Si configuramos todos los bits de arr[i] actual, es decir, digamos arr[i]=10 (1010),
• y lo cambiamos a 15 (1111),
• y el OR máximo actual calculado hasta ahora es mayor que 15,
• entonces no necesitamos comprobar si hay arr[i], ya que no afectará a nuestra ans.

Esto parece un cambio pequeño pero reducirá el tiempo significativamente.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum OR
int maxOR(vector<int>& nums)
{
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (ans >= pow(
                       2, floor(log2(nums[i]) + 1))
                       - 1)
            continue;
        for (int j = 0; j < n; j++) {
            if (i != j)
                ans = max(ans,
                          nums[i] | nums[j]);
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
 
    vector<int> arr = { 1, 2, 3, 4, 5, 6, 7 };
    cout << maxOR(arr) << endl;
 
    return 0;
}

// JAVA implementation of the above approach
import java.util.*;
class GFG
{
 
  // Function to return the maximum OR
  public static int maxOR(ArrayList<Integer> nums)
  {
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
      if (ans >= Math.pow(2, Math.floor(
        Math.log(nums.get(i)) + 1)) - 1)
        continue;
      for (int j = 0; j < n; j++) {
        if (i != j)
          ans = Math.max(ans, nums.get(i)
                         | nums.get(j));
      }
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    ArrayList<Integer> arr = new ArrayList<>(
      Arrays.asList(1, 2, 3, 4, 5, 6, 7));
    System.out.println(maxOR(arr));
  }
}
 
// This code is contributed by Taranpreet

# Python code for the above approach
# Function to return the maximum OR
from math import pow, floor, log2
 
def maxOR(nums):
    n = len(nums)
    ans = 0
    for i in range(n):
        if (ans >= pow(2, floor(log2(nums[i]) + 1)) - 1):
            continue
        for j in range(n):
            if (i != j):
                ans = max(ans, nums[i] | nums[j])
 
    return ans
 
# Driver Code
arr = [1, 2, 3, 4, 5, 6, 7]
print(maxOR(arr))
 
# This code is contributed by gfgking

// C# implementation of the above approach
using System;
class GFG
{
 
  // Function to return the maximum OR
  public static int maxOR(int[] nums)
  {
    int n = nums.Length;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
      if (ans >= Math.Pow(2, Math.Floor(
        Math.Log(nums[i]) + 1)) - 1)
        continue;
      for (int j = 0; j < n; j++)
      {
        if (i != j)
          ans = Math.Max(ans, nums[i]
                         | nums[j]);
      }
    }
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
    Console.Write(maxOR(arr));
  }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
       // JavaScript code for the above approach
       // Function to return the maximum OR
       function maxOR(nums) {
           let n = nums.length;
           let ans = 0;
           for (let i = 0; i < n; i++) {
               if (ans >= Math.pow(
                   2, Math.floor(Math.log2(nums[i]) + 1))
                   - 1)
                   continue;
               for (let j = 0; j < n; j++) {
                   if (i != j)
                       ans = Math.max(ans,
                           nums[i] | nums[j]);
               }
           }
           return ans;
       }
 
       // Driver Code
       let arr = [1, 2, 3, 4, 5, 6, 7];
       document.write(maxOR(arr) + '<br>');
 
      // This code is contributed by Potta Lokesh
   </script>

7

Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)