Dados 3 enteros A , B , C , la tarea es encontrar el valor XOR máximo de tres números seleccionados uno de cada rango [0, A], [0, B], [0, C] respectivamente.
Ejemplo:
Entrada: A = 1, B = 2, C = 4
Salida: 7
Explicación: El XOR máximo se puede calcular seleccionando 1 (de [0, 1]), 2 (de [0, 2]) y 4 (de [0 , 4]) es decir, 1⊕ 2⊕ 4 = 7Entrada: A = 6, B = 2, C = 10
Salida: 15
Explicación: El XOR máximo se puede calcular seleccionando 5 (de [0, 6]), 1 (de [0, 2]) y 10 (de [0 , 10]), es decir, 5⊕ 1⊕ 10 = 15.
Enfoque ingenuo: genere todos los tripletes posibles en los rangos anteriores y calcule el XOR máximo posible.
Complejidad de tiempo: O(A*B*C)
Espacio Auxiliar: O(1)
Enfoque eficiente:
Para encontrar el valor más grande de una operación XOR, el valor de XOR debe tener todos los bits para ser un bit establecido, es decir, en un número de 32 bits, el objetivo es obtener la mayor cantidad de 1 conjunto comenzando de izquierda a derecha. Esto se puede hacer siguiendo los siguientes pasos:
- Cree una variable ans que almacenará el valor del máximo xor posible y lo inicializará a cero.
- Para crear un valor de 32 bits que sea el máximo xor posible, ejecute un ciclo para cada uno de sus bits desde el bit más significativo hasta el bit menos significativo.
- Ahora para cada bit:
- Cree una variable cur que almacenará el número mínimo en el que se establece ese bit.
- Verifique cada rango A, B, C e intente encontrar un número que tenga un bit establecido en esa posición. Esto se puede hacer comparando A, B y C con cur, es decir, si cualquier número de A, B y C es mayor o igual que cur, entonces contendrá un bit establecido en esa posición. Si se encuentra un bit establecido en cualquiera de los números de A, B, C, entonces el xor máximo también contendrá un bit establecido en esa posición.
- Ahora, si se encuentra un bit establecido, agregue cur a ans para establecer ese bit en él, y disminuya el valor del número en el que se encuentra el bit establecido (de A, B, C) por cur para desactivar ese bit como no se puede volver a utilizar.
- Realice los pasos anteriores para cada bit, para calcular el valor final de la respuesta.
- Después de los pasos anteriores, imprima el resultado requerido.
Implementación:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// maximum triplet XOR form 3 ranges
int maximumTripletXOR(int A, int B, int C)
{
// Initialize a variable
// to store the answer
int ans = 0;
for (int i = 30; i >= 0; i--) {
// create minimum number
// that have a set bit
// at ith position
int cur = 1 << i;
// Check for each number
// and try to greedily choose
// the bit if possible
// If A >= cur then A also have a
// set bit at ith position
if (A >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from A
A -= cur;
}
// Check for B
else if (B >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from B
B -= cur;
}
// Check for C
else if (C >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from C
C -= cur;
}
// If any of the above conditions
// is not satisfied then
// there is no way to turn that bit ON.
}
return ans;
}
// Driver Code
int main()
{
int A = 6;
int B = 2;
int C = 10;
cout << maximumTripletXOR(A, B, C);
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to calculate
// maximum triplet XOR form 3 ranges
static int maximumTripletXOR(int A, int B, int C)
{
// Initialize a variable
// to store the answer
int ans = 0;
for (int i = 30; i >= 0; i--) {
// create minimum number
// that have a set bit
// at ith position
int cur = 1 << i;
// Check for each number
// and try to greedily choose
// the bit if possible
// If A >= cur then A also have a
// set bit at ith position
if (A >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from A
A -= cur;
}
// Check for B
else if (B >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from B
B -= cur;
}
// Check for C
else if (C >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from C
C -= cur;
}
// If any of the above conditions
// is not satisfied then
// there is no way to turn that bit ON.
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int A = 6;
int B = 2;
int C = 10;
System.out.print(maximumTripletXOR(A, B, C));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python Program to implement # the above approach # Function to calculate # maximum triplet XOR form 3 ranges def maximumTripletXOR(A, B, C): # Initialize a variable # to store the answer ans = 0 for i in range(30, -1,-1): # create minimum number # that have a set bit # at ith position cur = 1 << i # Check for each number # and try to greedily choose # the bit if possible # If A >= cur then A also have a # set bit at ith position if (A >= cur): # Increment the answer ans += cur # Subtract this value from A A -= cur # Check for B elif (B >= cur): # Increment the answer ans += cur # Subtract this value from B B -= cur # Check for C elif (C >= cur): # Increment the answer ans += cur # Subtract this value from C C -= cur # If any of the above conditions # is not satisfied then # there is no way to turn that bit ON. return ans # Driver Code A = 6 B = 2 C = 10 print(maximumTripletXOR(A, B, C)) # This code is contributed by shivanisinghss2110
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to calculate
// maximum triplet XOR form 3 ranges
static int maximumTripletXOR(int A, int B, int C)
{
// Initialize a variable
// to store the answer
int ans = 0;
for (int i = 30; i >= 0; i--) {
// create minimum number
// that have a set bit
// at ith position
int cur = 1 << i;
// Check for each number
// and try to greedily choose
// the bit if possible
// If A >= cur then A also have a
// set bit at ith position
if (A >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from A
A -= cur;
}
// Check for B
else if (B >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from B
B -= cur;
}
// Check for C
else if (C >= cur) {
// Increment the answer
ans += cur;
// Subtract this value from C
C -= cur;
}
// If any of the above conditions
// is not satisfied then
// there is no way to turn that bit ON.
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int A = 6;
int B = 2;
int C = 10;
Console.Write(maximumTripletXOR(A, B, C));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to calculate maximum
// triplet XOR form 3 ranges
function maximumTripletXOR(A, B, C)
{
// Initialize a variable
// to store the answer
let ans = 0;
for(let i = 30; i >= 0; i--)
{
// Create minimum number
// that have a set bit
// at ith position
let cur = 1 << i;
// Check for each number
// and try to greedily choose
// the bit if possible
// If A >= cur then A also have a
// set bit at ith position
if (A >= cur)
{
// Increment the answer
ans += cur;
// Subtract this value from A
A -= cur;
}
// Check for B
else if (B >= cur)
{
// Increment the answer
ans += cur;
// Subtract this value from B
B -= cur;
}
// Check for C
else if (C >= cur)
{
// Increment the answer
ans += cur;
// Subtract this value from C
C -= cur;
}
// If any of the above conditions
// is not satisfied then
// there is no way to turn that bit ON.
}
return ans;
}
// Driver Code
let A = 6;
let B = 2;
let C = 10;
document.write(maximumTripletXOR(A, B, C));
// This code is contributed by Potta Lokesh
</script>
Producción
15
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA