Dada una array arr[] que consta de N enteros, la tarea es encontrar un entero K , que no tenga más de los bits máximos presentes en ningún elemento de la array, que cuando se agrega a la array, maximiza el Bitwise XOR de la array.
Ejemplos:
Entrada: N = 7, arr[] = {1, 7, 8, 11, 6, 9, 6}
Salida: 3
Explicación:
XOR bit a bit de la array dada = 1 ^ 7 ^ 8 ^ 11 ^ 6 ^ 9 ^ 6 = 12
(12) 2 = (1100) 2
(0011) 2 = (3) 10 es la mejor opción para maximizar el XOR de la array.
Por lo tanto, 12 ^ 3 = 15 es el XOR máximo posible de la array dada.Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}
Salida: 6
Explicación:
XOR bit a bit de la array dada = 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1
(1) 2 = ( 0001) 2
(0110) 2 = (6) 10 es la mejor opción para maximizar el XOR de la array.
Por lo tanto, 1 ^ 6 = 7 es el XOR máximo posible de la array dada.
Enfoque: siga los pasos a continuación para resolver el problema:
- Calcule el Bitwise XOR de todos los elementos de la array
- Calcule el complemento del XOR calculado de los elementos de la array de modo que el número de bits en el complemento sea igual al máximo de bits presentes en cualquier elemento de la array.
- El complemento de XOR es el valor requerido que se agregará para maximizar el XOR bit a bit de la array dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find complement of an integer
unsigned int onesComplement(unsigned int n,
int maxElement)
{
// Count the number of bits of maxElement
int bits = floor(log2(maxElement)) + 1;
// Return 1's complement
return ((1 << bits) - 1) ^ n;
}
// Function to find the value required to be
// added to maximize XOR of the given array
int findNumber(int arr[], int n)
{
// Stores the required value
// to be added to the array
unsigned int res = 0;
// Stores the maximum array element
int maxElement = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Update XOR of the array
res = res ^ arr[i];
// Find maximum element in array
if (maxElement < arr[i])
maxElement = arr[i];
}
// Calculate 1s' complement
res = onesComplement(res,
maxElement);
// Return the answer
return (res);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findNumber(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
import java.lang.*;
class GFG{
// Function to find complement of an integer
static int onesComplement(int n,
int maxElement)
{
// Count the number of bits of maxElement
int bits = (int)Math.floor((
Math.log(maxElement) /
Math.log(2))) + 1 ;
// Return 1's complement
return ((1 << bits) - 1) ^ n;
}
// Function to find the value required to be
// added to maximize XOR of the given array
static int findNumber(int arr[], int n)
{
// Stores the required value
// to be added to the array
int res = 0;
// Stores the maximum array element
int maxElement = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// Update XOR of the array
res = res ^ arr[i];
// Find maximum element in array
if (maxElement < arr[i])
maxElement = arr[i];
}
// Calculate 1s' complement
res = onesComplement(res,
maxElement);
// Return the answer
return (res);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = arr.length;
System.out.print(findNumber(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python program for the above approach import math # Function to find complement of an integer def onesComplement(n, maxElement) : # Count the number of bits of maxElement bits = math.floor(math.log2(maxElement)) + 1 # Return 1's complement return ((1 << bits) - 1) ^ n # Function to find the value required to be # added to maximize XOR of the given array def findNumber(arr, n) : # Stores the required value # to be added to the array res = 0 # Stores the maximum array element maxElement = 0 # Traverse the array for i in range(n): # Update XOR of the array res = res ^ arr[i] # Find maximum element in array if (maxElement < arr[i]): maxElement = arr[i] # Calculate 1s' complement res = onesComplement(res, maxElement) # Return the answer return (res) # Driver Code arr = [ 1, 2, 3, 4, 5 ] N = len(arr) print(findNumber(arr, N)) # This code is contributed by code_hunt.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find complement of an integer
static int onesComplement(int n,
int maxElement)
{
// Count the number of bits of maxElement
int bits = (int)Math.Floor((
Math.Log(maxElement) /
Math.Log(2))) + 1 ;
// Return 1's complement
return ((1 << bits) - 1) ^ n;
}
// Function to find the value required to be
// added to maximize XOR of the given array
static int findNumber(int[] arr, int n)
{
// Stores the required value
// to be added to the array
int res = 0;
// Stores the maximum array element
int maxElement = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// Update XOR of the array
res = res ^ arr[i];
// Find maximum element in array
if (maxElement < arr[i])
maxElement = arr[i];
}
// Calculate 1s' complement
res = onesComplement(res,
maxElement);
// Return the answer
return (res);
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int N = arr.Length;
Console.Write(findNumber(arr, N));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program for above approach
// Function to find complement of an integer
function onesComplement(n,
maxElement)
{
// Count the number of bits of maxElement
let bits = Math.floor((
Math.log(maxElement) /
Math.log(2))) + 1 ;
// Return 1's complement
return ((1 << bits) - 1) ^ n;
}
// Function to find the value required to be
// added to maximize XOR of the given array
function findNumber(arr, n)
{
// Stores the required value
// to be added to the array
let res = 0;
// Stores the maximum array element
let maxElement = 0;
// Traverse the array
for(let i = 0; i < n; i++)
{
// Update XOR of the array
res = res ^ arr[i];
// Find maximum element in array
if (maxElement < arr[i])
maxElement = arr[i];
}
// Calculate 1s' complement
res = onesComplement(res,
maxElement);
// Return the answer
return (res);
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5 ];
let N = arr.length;
document.write(findNumber(arr, N));
// This code is contributed by avijitmondal1998.
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por parthbanathia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA