Maximice Bitwise AND de Array reemplazando como máximo un elemento

Dada una array arr[] que contiene N enteros positivos, la tarea es maximizar AND bit a bit de arr[] seleccionando como máximo un elemento de arr[] e incrementarlo o disminuirlo en cualquier valor.

Ejemplos:

Entrada: arr[] = {1, 2, 3}
Salida: 2
Explicación: Las siguientes son las operaciones realizadas para maximizar el AND bit a bit de arr[]
Inicialmente AND bit a bit de {1, 2, 3} = 0
Incrementando arr[0] por 1 actualiza arr[] = {2, 2, 3}. 
Ahora AND bit a bit de {2, 2, 3} es 2, que es el máximo posible. 
Por lo tanto, la respuesta es 2. 

Entrada: arr[] = {10, 10}
Salida: 10
Explicación: No realice ninguna operación que sea óptima.  

Enfoque: La declaración del problema de este problema dice maximizar AND de arr[] reemplazando casi un elemento de arr[] . El método de fuerza bruta para resolver este problema es tomar AND bit a bit de todos los elementos en arr[] excepto uno a la vez y encontrar un reemplazo apropiado para ese elemento cuya contribución no se agrega en todo el AND bit a bit de arr[] cada vez . Haga esto para todos los elementos en arr[] y encuentre el resultado óptimo. 

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

#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum AND by
// Replacing atmost one element by any value
int maxAnd(int n, vector<int> a)
{
    // To Calculate answer
    int ans = 0;
 
    // Iterating through the array
    for (int i = 0; i < n; i++) {
        int max_and = 0XFFFFFFFF;
 
        // Checking and for element and
        // Leaving only jth element
        for (int j = 0; j < n; j++) {
            if (i != j) {
                max_and = max_and & a[j];
            }
        }
 
        // Comparing previous answers
        // and max answers
        ans = max(ans, max_and);
    }
    return ans;
}
 
// Driver Code
int main()
{
    int N = 3;
    vector<int> arr = { 1, 2, 3 };
 
    // Function Call
    cout << maxAnd(N, arr) << "\n";
}

import java.io.*;
 
class GFG{
   
// Function to find maximum AND by
// Replacing atmost one element by any value
static int maxAnd(int n,int[] a)
{
     
    // To Calculate answer
    int ans = 0;
 
    // Iterating through the array
    for(int i = 0; i < n; i++)
    {
        int max_and = 0XFFFFFFFF;
 
        // Checking and for element and
        // Leaving only jth element
        for(int j = 0; j < n; j++)
        {
            if (i != j)
            {
                max_and = max_and & a[j];
            }
        }
 
        // Comparing previous answers
        // and max answers
        ans = Math.max(ans, max_and);
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
    int[] arr = { 1, 2, 3 };
     
    // Function Call
    System.out.println( maxAnd(N, arr) );
}
}
 
// This code is contributed by Potta Lokesh

# Function to find maximum AND by
# Replacing atmost one element by any value
def maxAnd(n, a):
     
    # To Calculate answer
    ans = 0
 
    # Iterating through the array
    for i in range(0, n):
        max_and = 0XFFFFFFFF
 
        # Checking and for element and
        # Leaving only jth element
        for j in range(0, n):
            if (i != j):
                max_and = max_and & a[j]
 
        # Comparing previous answers
        # and max answers
        ans = max(ans, max_and)
         
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    N = 3
    arr = [ 1, 2, 3 ]
     
    print(maxAnd(N, arr))
     
    # This code is contributed by Samim Hossain Mondal.

using System;
 
class GFG{
   
// Function to find maximum AND by
// Replacing atmost one element by any value
static int maxAnd(int n,int[] a)
{
     
    // To Calculate answer
    int ans = 0;
 
    // Iterating through the array
    for(int i = 0; i < n; i++)
    {
        uint max_and = 0XFFFFFFFF;
 
        // Checking and for element and
        // Leaving only jth element
        for(int j = 0; j < n; j++)
        {
            if (i != j)
            {
                max_and = Convert.ToUInt32(max_and & a[j]);
            }
        }
 
        // Comparing previous answers
        // and max answers
        ans = Math.Max(ans, (int)max_and);
    }
    return ans;
}
 
// Driver Code
public static void Main()
{
    int N = 3;
    int[] arr = { 1, 2, 3 };
     
    // Function Call
    Console.Write( maxAnd(N, arr) );
}
}
 
// This code is contributed by gfgking

<script>
 
// Function to find maximum AND by
// Replacing atmost one element by any value
const maxAnd = (n, a) => {
     
    // To Calculate answer
    let ans = 0;
 
    // Iterating through the array
    for(let i = 0; i < n; i++)
    {
        let max_and = 0XFFFFFFFF;
 
        // Checking and for element and
        // Leaving only jth element
        for(let j = 0; j < n; j++)
        {
            if (i != j)
            {
                max_and = max_and & a[j];
            }
        }
 
        // Comparing previous answers
        // and max answers
        ans = Math.max(ans, max_and);
    }
    return ans;
}
 
// Driver Code
let N = 3;
let arr = [ 1, 2, 3 ];
 
// Function Call
document.write(maxAnd(N, arr));
 
// This code is contributed by rakeshsahni
 
</script>

2

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