Nos dan una array de n elementos positivos. necesitamos encontrar el valor AND máximo generado por cualquier par de elementos de la array. AND es bit a bit & operador.
Ejemplos:
Input : arr[] = {4, 8, 12, 16}
Output : Maximum AND value = 8
Input : arr[] = {4, 8, 16, 2}
Output : Maximum AND value = 0
Enfoque ingenuo: el enfoque básico es el mismo que el valor xor máximo. Iteramos sobre todos los pares posibles y calculamos el valor AND de todos ellos. Elija el valor más grande entre ellos.
C++
// CPP Program to find maximum XOR value of a pair
#include<bits/stdc++.h>
using namespace std;
// Function for finding maximum and value pair
int maxAND(int arr[], int n)
{
int res = 0;
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
res = max(res, arr[i] & arr[j]);
return res;
}
// Driver function
int main()
{
int arr[] = {4, 8, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum AND Value = " << maxAND(arr,n);
return 0;
}
Java
// Java Program to find maximum
// XOR value of a pair
import java.util.*;
import java.lang.*;
public class GfG{
// Function for finding maximum
// and value pair
static int maxAND(int arr[], int n)
{
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
res = res > ( arr[i] & arr[j]) ?
res : ( arr[i] & arr[j]);
return res;
}
// driver function
public static void main(String argc[])
{
int arr[] = {4, 8, 6, 2};
int n = arr.length;
System.out.println("Maximum AND Value = " +
maxAND(arr,n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 Program to find maximum XOR
# value of a pair
# Function for finding maximum and value pair
def maxAND(arr, n) :
res = 0
for i in range(0, n) :
for j in range(i + 1, n) :
res = max(res, arr[i] & arr[j])
return res
# Driver function
arr = [4, 8, 6, 2]
n = len(arr)
print("Maximum AND Value = ", maxAND(arr,n))
# This code is contributed by Nikita Tiwari.
C#
// C# Program to find maximum
// XOR value of a pair
using System;
public class GfG
{
// Function for finding maximum
// and value pair
static int maxAND(int []arr, int n)
{
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
res = res > ( arr[i] & arr[j]) ?
res : ( arr[i] & arr[j]);
return res;
}
// Driver code
public static void Main()
{
int []arr = {4, 8, 6, 2};
int n = arr.Length;
Console.WriteLine("Maximum AND Value = " +
maxAND(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find maximum
// XOR value of a pair
// Function for finding
// maximum and value pair
function maxAND($arr, $n)
{
$res = 0;
for ($i = 0; $i < $n; $i++)
for ($j = $i + 1; $j < $n; $j++)
$res = max($res, $arr[$i] &
$arr[$j]);
return $res;
}
// Driver Code
$arr = array(4, 8, 6, 2);
$n = count($arr);
echo "Maximum AND Value = " , maxAND($arr, $n);
// This code is contributed by vt_m.
?>
Javascript
<script>
// Javascript Program to find maximum XOR value of a pair
// Function for finding maximum and value pair
function maxAND(arr, n)
{
var res = 0;
for (var i=0; i<n; i++)
for (var j=i+1; j<n; j++)
res = Math.max(res, arr[i] & arr[j]);
return res;
}
// Driver function
var arr = [4, 8, 6, 2];
var n = arr.length;
document.write( "Maximum AND Value = " + maxAND(arr,n));
</script>
Producción
Maximum AND Value = 4
Complejidad temporal: O(n*n)
Espacio auxiliar: O(1)
Mejor enfoque: la idea se basa en las propiedades del operador AND. La operación AND de dos bits cualquiera da como resultado 1 si ambos bits son 1. Comenzamos desde el MSB y verificamos si tenemos un mínimo de dos elementos de array que tengan un valor establecido. En caso afirmativo, ese MSB será parte de nuestra solución y se agregará al resultado; de lo contrario, descartaremos ese bit. De manera similar, al iterar de MSB a LSB (32 a 1) para la posición del bit, podemos verificar fácilmente qué bit será parte de nuestra solución y seguiremos agregando todos esos bits a nuestra solución.
Explicación: Consideremos el primer ejemplo de {4, 8, 12, 16}:
NOTA : El patrón aquí representa res | 1<< bit, es decir, agregaremos un bit a partir de MSB para verificar si el patrón después de agregar este bit puede ser nuestra respuesta al contar cuántos no. en la array tiene este mismo patrón, si se vuelve mayor que igual a 2, lo agregamos.
- paso 1 : Escriba la representación de bits de cada elemento:
4 = 100, 8 = 1000, 12 = 1100, 16 = 10000- paso 2 : verifique el 1er MSB, patrón = 0 + 16 = 16 significa que tenemos 10000 como nuestro patrón en equivalente binario. Ahora se establece el quinto bit en 16, pero ningún otro elemento tiene 5 bits como bit establecido, por lo que esto no se sumará a nuestro RES, todavía RES = 0 y patrón = 0
- paso 3: Verifique el 4to bit, patrón = 0 + 8 = 8 significa que tenemos 1000 como nuestro patrón en equivalente binario. Ahora, tanto el 8 como el 12 tienen un bit establecido en la posición del cuarto bit, por lo que se sumarán en nuestra solución, RES = 8 y patrón = 8, es decir, RES = 1000 y patrón = 1000.
- Paso 4: Verifique el 3er bit, patrón = 8 + 4 = 12. Es decir, después de agregar el 3er bit, nuestro patrón se convierte en 1100. Cuando verificamos cuántos no. en la array que tiene este patrón, encontramos que ahora solo 12 lo satisface menos dos números. entonces descartaremos el 3er bit, RES = 8 (1000) y patrón = 8 (1000)
- Paso 5: verifique el segundo bit, patrón = 8 + 2 = 10, después de agregar el segundo bit, nuestro patrón se convierte en 1010. Cuando verificamos cuántos no. en la array que tiene este patrón, no encontramos ningún elemento que tenga este patrón dentro, es decir. Ningún elemento ha establecido un bit igual que el patrón, por lo que descartaremos el segundo bit, RES = 8 (1000) y patrón = 8 (1000).
- paso 4: compruebe el primer bit, patrón = 8 + 1 = 9, es decir. es decir, después de agregar el 3er bit, nuestro patrón se convierte en 1001. Ningún elemento ha establecido el mismo bit que el patrón, por lo que descartaremos el 1er bit, RES = 8 (1000) y patrón = 8 (1000).
Implementación:
C++
// CPP Program to find maximum XOR value of a pair
#include<bits/stdc++.h>
using namespace std;
// Utility function to check number of elements
// having set msb as of pattern
int checkBit(int pattern, int arr[], int n)
{
int count = 0;
for (int i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
// Function for finding maximum and value pair
int maxAND (int arr[], int n)
{
int res = 0, count;
// iterate over total of 32bits from msb to lsb
for (int bit = 31; bit >= 0; bit--)
{
// find the count of element having same pattern as obtained by adding bits on every iteration.
count = checkBit(res | (1 << bit),arr,n);
// if count >= 2 set particular bit in result
if ( count >= 2 )
res = res | (1 << bit); // this is the pattern we continued
}
return res;
}
// Driver function
int main()
{
int arr[] = {4, 8, 6, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum AND Value = " << maxAND(arr,n);
return 0;
}
Java
// Java Program to find maximum
// XOR value of a pair
import java.util.*;
import java.lang.*;
public class GfG{
// Utility function to check number of elements
// having set msb as of pattern
static int checkBit(int pattern, int arr[], int n)
{
int count = 0;
for (int i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
// Function for finding maximum and value pair
static int maxAND (int arr[], int n)
{
int res = 0, count;
// iterate over total of 32bits
// from msb to lsb
for (int bit = 31; bit >= 0; bit--)
{
// find the count of element
// having set msb
count = checkBit(res | (1 << bit), arr, n);
// if count >= 2 set particular
// bit in result
if ( count >= 2 )
res |= (1 << bit);
}
return res;
}
// driver function
public static void main(String argc[])
{
int arr[] = {4, 8, 6, 2};
int n = arr.length;
System.out.println("Maximum AND Value = " +
maxAND(arr, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 Program to find maximum XOR
# value of a pair
# Utility function to check number of
# elements having set msb as of pattern
def checkBit(pattern,arr, n) :
count = 0
for i in range(0, n) :
if ((pattern & arr[i]) == pattern) :
count = count + 1
return count
# Function for finding maximum and
# value pair
def maxAND (arr, n) :
res = 0
# iterate over total of 32bits
# from msb to lsb
for bit in range(31,-1,-1) :
# find the count of element
# having set msb
count = checkBit(res | (1 << bit), arr, n)
# if count >= 2 set particular
# bit in result
if ( count >= 2 ) :
res =res | (1 << bit)
return res
# Driver function
arr = [4, 8, 6, 2]
n = len(arr)
print("Maximum AND Value = ", maxAND(arr, n))
# This code is contributed by Nikita Tiwari
C#
// C# Program to find maximum
// XOR value of a pair
using System;
public class GfG
{
// Utility function to check
// number of elements having
// set msb as of pattern
static int checkBit(int pattern,
int []arr,
int n)
{
int count = 0;
for (int i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
// Function for finding maximum
// and value pair
static int maxAND (int []arr, int n)
{
int res = 0, count;
// iterate over total of 32bits
// from msb to lsb
for (int bit = 31; bit >= 0; bit--)
{
// find the count of element
// having set msb
count = checkBit(res | (1 << bit), arr, n);
// if count >= 2 set particular
// bit in result
if (count >= 2)
res |= (1 << bit);
}
return res;
}
// Driver Code
public static void Main()
{
int []arr = {4, 8, 6, 2};
int n = arr.Length;
Console.WriteLine("Maximum AND Value = " +
maxAND(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find maximum
// XOR value of a pair
// Utility function to check
// number of elements having
// set msb as of pattern
function checkBit($pattern, $arr, $n)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
if (($pattern & $arr[$i]) == $pattern)
$count++;
return $count;
}
// Function for finding
// maximum and value pair
function maxAND ($arr, $n)
{
$res = 0;$count;
// iterate over total of
// 32bits from msb to lsb
for ($bit = 31; $bit >= 0; $bit--)
{
// find the count of element
// having set msb
$count = checkBit($res | (1 << $bit),
$arr, $n);
// if count >= 2 set particular
// bit in result
if ( $count >= 2 )
$res |= (1 << $bit);
}
return $res;
}
// Driver Code
$arr = array(4, 8, 6, 2);
$n = count($arr);
echo "Maximum AND Value = " , maxAND($arr,$n);
// This code is contributed by vt_m.
?>
Javascript
<script>
// Javascript Program to find maximum XOR value of a pair
// Utility function to check
// number of elements having
// set msb as of pattern
function checkBit(pattern, arr, n)
{
let count = 0;
for (let i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
// Function for finding maximum
// and value pair
function maxAND (arr, n)
{
let res = 0, count;
// iterate over total of 32bits
// from msb to lsb
for (let bit = 31; bit >= 0; bit--)
{
// find the count of element
// having set msb
count = checkBit(res | (1 << bit), arr, n);
// if count >= 2 set particular
// bit in result
if (count >= 2)
res |= (1 << bit);
}
return res;
}
let arr = [4, 8, 6, 2];
let n = arr.length;
document.write("Maximum AND Value = " + maxAND(arr, n));
// This code is contributed by divyesh072019.
</script>
Producción
Maximum AND Value = 4
Complejidad de tiempo: O(n * log(m)) donde m es el elemento máximo de la array y n es el tamaño de la array.
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA