Se le da una secuencia de N enteros y Q consultas. En cada consulta, se le dan dos parámetros L y R. Tiene que encontrar el entero más pequeño X tal que 0 <= X < 2^31 y la suma de XOR de x con todos los elementos es el rango [L, R] es máximo posible.
Ejemplos:
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645
Planteamiento: La representación binaria de cada elemento y X, podemos observar que cada bit es independiente y el problema se puede resolver iterando sobre cada bit. Ahora, básicamente, para cada bit, necesitamos contar la cantidad de 1 y 0 en el rango dado, si la cantidad de 1 es mayor, debe establecer ese bit de X en 0 para que la suma sea máxima después de x o con X, de lo contrario si el número de 0 es mayor, entonces debe configurar ese bit de X en 1. Si el número de 1 y 0 es igual, entonces podemos configurar ese bit de X en cualquiera de 1 o 0 porque no afectará la suma, pero tenemos que minimizar el valor de X por lo que tomaremos ese bit 0.
Ahora, para optimizar la solución, podemos precalcular el conteo de 1 en cada posición de bit de los números hasta esa posición haciendo una array de prefijos, esto tomará O (n) tiempo. Ahora, para cada consulta, el número de 1 será el número de 1 hasta la posición R – el número de 1 hasta la posición (L-1).
C++
// CPP program to find smallest integer X
// such that sum of its XOR with range is
// maximum.
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647
int one[100001][32];
// Function to make prefix array which
// counts 1's of each bit up to that number
void make_prefix(int A[], int n)
{
for (int j = 0; j < 32; j++)
one[0][j] = 0;
// Making a prefix array which sums
// number of 1's up to that position
for (int i = 1; i <= n; i++)
{
int a = A[i - 1];
for (int j = 0; j < 32; j++)
{
int x = pow(2, j);
// If j-th bit of a number is set then
// add one to previously counted 1's
if (a & x)
one[i][j] = 1 + one[i - 1][j];
else
one[i][j] = one[i - 1][j];
}
}
}
// Function to find X
int Solve(int L, int R)
{
int l = L, r = R;
int tot_bits = r - l + 1;
// Initially taking maximum value all bits 1
int X = MAX;
// Iterating over each bit
for (int i = 0; i < 31; i++)
{
// get 1's at ith bit between the
// range L-R by subtracting 1's till
// Rth number - 1's till L-1th number
int x = one[r][i] - one[l - 1][i];
// If 1's are more than or equal to 0's
// then unset the ith bit from answer
if (x >= tot_bits - x)
{
int ith_bit = pow(2, i);
// Set ith bit to 0 by doing
// Xor with 1
X = X ^ ith_bit;
}
}
return X;
}
// Driver program
int main()
{
// Taking inputs
int n = 5, q = 3;
int A[] = { 210, 11, 48, 22, 133 };
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 };
make_prefix(A, n);
for (int j = 0; j < q; j++)
cout << Solve(L[j], R[j]) << endl;
return 0;
}
Java
// Java program to find smallest integer X
// such that sum of its XOR with range is
// maximum.
import java.lang.Math;
class GFG {
private static final int MAX = 2147483647;
static int[][] one = new int[100001][32];
// Function to make prefix array which counts
// 1's of each bit up to that number
static void make_prefix(int A[], int n)
{
for (int j = 0; j < 32; j++)
one[0][j] = 0;
// Making a prefix array which sums
// number of 1's up to that position
for (int i = 1; i <= n; i++)
{
int a = A[i - 1];
for (int j = 0; j < 32; j++)
{
int x = (int)Math.pow(2, j);
// If j-th bit of a number is set then
// add one to previously counted 1's
if ((a & x) != 0)
one[i][j] = 1 + one[i - 1][j];
else
one[i][j] = one[i - 1][j];
}
}
}
// Function to find X
static int Solve(int L, int R)
{
int l = L, r = R;
int tot_bits = r - l + 1;
// Initially taking maximum
// value all bits 1
int X = MAX;
// Iterating over each bit
for (int i = 0; i < 31; i++)
{
// get 1's at ith bit between the range
// L-R by subtracting 1's till
// Rth number - 1's till L-1th number
int x = one[r][i] - one[l - 1][i];
// If 1's are more than or equal to 0's
// then unset the ith bit from answer
if (x >= tot_bits - x)
{
int ith_bit = (int)Math.pow(2, i);
// Set ith bit to 0 by
// doing Xor with 1
X = X ^ ith_bit;
}
}
return X;
}
// Driver program
public static void main(String[] args)
{
// Taking inputs
int n = 5, q = 3;
int A[] = { 210, 11, 48, 22, 133 };
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 };
make_prefix(A, n);
for (int j = 0; j < q; j++)
System.out.println(Solve(L[j], R[j]));
}
}
// This code is contributed by Smitha
Python3
# Python3 program to find smallest integer X # such that sum of its XOR with range is # maximum. import math one = [[0 for x in range(32)] for y in range(100001)] MAX = 2147483647 # Function to make prefix array # which counts 1's of each bit # up to that number def make_prefix(A, n) : global one, MAX for j in range(0 , 32) : one[0][j] = 0 # Making a prefix array which # sums number of 1's up to # that position for i in range(1, n+1) : a = A[i - 1] for j in range(0 , 32) : x = int(math.pow(2, j)) # If j-th bit of a number # is set then add one to # previously counted 1's if (a & x) : one[i][j] = 1 + one[i - 1][j] else : one[i][j] = one[i - 1][j] # Function to find X def Solve(L, R) : global one, MAX l = L r = R tot_bits = r - l + 1 # Initially taking maximum # value all bits 1 X = MAX # Iterating over each bit for i in range(0, 31) : # get 1's at ith bit between the # range L-R by subtracting 1's till # Rth number - 1's till L-1th number x = one[r][i] - one[l - 1][i] # If 1's are more than or equal # to 0's then unset the ith bit # from answer if (x >= (tot_bits - x)) : ith_bit = pow(2, i) # Set ith bit to 0 by # doing Xor with 1 X = X ^ ith_bit return X # Driver Code n = 5 q = 3 A = [ 210, 11, 48, 22, 133 ] L = [ 1, 4, 2 ] R = [ 3, 14, 4 ] make_prefix(A, n) for j in range(0, q) : print (Solve(L[j], R[j]),end="\n") # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# program to find smallest integer X
// such that sum of its XOR with range is
// maximum.
using System;
using System.Collections.Generic;
class GFG{
static int MAX = 2147483647;
static int [,]one = new int[100001,32];
// Function to make prefix
// array which counts 1's
// of each bit up to that number
static void make_prefix(int []A, int n)
{
for (int j = 0; j < 32; j++)
one[0,j] = 0;
// Making a prefix array which sums
// number of 1's up to that position
for (int i = 1; i <= n; i++)
{
int a = A[i - 1];
for (int j = 0; j < 32; j++)
{
int x = (int)Math.Pow(2, j);
// If j-th bit of a number is set then
// add one to previously counted 1's
if ((a & x) != 0)
one[i, j] = 1 + one[i - 1, j];
else
one[i,j] = one[i - 1, j];
}
}
}
// Function to find X
static int Solve(int L, int R)
{
int l = L, r = R;
int tot_bits = r - l + 1;
// Initially taking maximum
// value all bits 1
int X = MAX;
// Iterating over each bit
for (int i = 0; i < 31; i++)
{
// get 1's at ith bit between the
// range L-R by subtracting 1's till
// Rth number - 1's till L-1th number
int x = one[r, i] - one[l - 1, i];
// If 1's are more than or
// equal to 0's then unset
// the ith bit from answer
if (x >= tot_bits - x)
{
int ith_bit = (int)Math.Pow(2, i);
// Set ith bit to 0 by doing
// Xor with 1
X = X ^ ith_bit;
}
}
return X;
}
// Driver Code
public static void Main()
{
// Taking inputs
int n = 5, q = 3;
int []A = {210, 11, 48, 22, 133};
int []L = {1, 4, 2};
int []R = {3, 14, 4};
make_prefix(A, n);
for (int j = 0; j < q; j++)
Console.WriteLine(Solve(L[j], R[j]));
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
PHP
<?php
error_reporting(0);
// PHP program to find smallest integer X
// such that sum of its XOR with range is
// maximum.
$one = array();
$MAX = 2147483647;
// Function to make prefix array
// which counts 1's of each bit
// up to that number
function make_prefix($A, $n)
{
global $one, $MAX;
for ($j = 0; $j < 32; $j++)
$one[0][$j] = 0;
// Making a prefix array which
// sums number of 1's up to
// that position
for ($i = 1; $i <= $n; $i++)
{
$a = $A[$i - 1];
for ($j = 0; $j < 32; $j++)
{
$x = pow(2, $j);
// If j-th bit of a number
// is set then add one to
// previously counted 1's
if ($a & $x)
$one[$i][$j] = 1 + $one[$i - 1][$j];
else
$one[$i][$j] = $one[$i - 1][$j];
}
}
}
// Function to find X
function Solve($L, $R)
{
global $one, $MAX;
$l = $L; $r = $R;
$tot_bits = $r - $l + 1;
// Initially taking maximum
// value all bits 1
$X = $MAX;
// Iterating over each bit
for ($i = 0; $i < 31; $i++)
{
// get 1's at ith bit between the
// range L-R by subtracting 1's till
// Rth number - 1's till L-1th number
$x = $one[$r][$i] - $one[$l - 1][$i];
// If 1's are more than or equal
// to 0's then unset the ith bit
// from answer
if ($x >= ($tot_bits - $x))
{
$ith_bit = pow(2, $i);
// Set ith bit to 0 by
// doing Xor with 1
$X = $X ^ $ith_bit;
}
}
return $X;
}
// Driver Code
$n = 5; $q = 3;
$A = [ 210, 11, 48, 22, 133 ];
$L = [ 1, 4, 2 ];
$R = [ 3, 14, 4 ];
make_prefix($A, $n);
for ($j = 0; $j < $q; $j++)
echo (Solve($L[$j], $R[$j]). "\n");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to find smallest integer X
// such that sum of its XOR with range is
// maximum.
const MAX = 2147483647;
let one = new Array(100001);
for (let i = 0; i < 100001; i++)
one[i] = new Array(32);
// Function to make prefix array which
// counts 1's of each bit up to that number
function make_prefix(A, n)
{
for (let j = 0; j < 32; j++)
one[0][j] = 0;
// Making a prefix array which sums
// number of 1's up to that position
for (let i = 1; i <= n; i++)
{
let a = A[i - 1];
for (let j = 0; j < 32; j++)
{
let x = Math.pow(2, j);
// If j-th bit of a number is set then
// add one to previously counted 1's
if (a & x)
one[i][j] = 1 + one[i - 1][j];
else
one[i][j] = one[i - 1][j];
}
}
}
// Function to find X
function Solve(L, R)
{
let l = L, r = R;
let tot_bits = r - l + 1;
// Initially taking maximum value all bits 1
let X = MAX;
// Iterating over each bit
for (let i = 0; i < 31; i++)
{
// get 1's at ith bit between the
// range L-R by subtracting 1's till
// Rth number - 1's till L-1th number
let x = one[r][i] - one[l - 1][i];
// If 1's are more than or equal to 0's
// then unset the ith bit from answer
if (x >= tot_bits - x)
{
let ith_bit = Math.pow(2, i);
// Set ith bit to 0 by doing
// Xor with 1
X = X ^ ith_bit;
}
}
return X;
}
// Driver program
// Taking inputs
let n = 5, q = 3;
let A = [ 210, 11, 48, 22, 133 ];
let L = [ 1, 4, 2 ], R = [ 3, 14, 4 ];
make_prefix(A, n);
for (let j = 0; j < q; j++)
document.write(Solve(L[j], R[j]) + "<br>");
</script>
Producción :
2147483629 2147483647 2147483629
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)
Enfoque 2
En la siguiente tabla, puede ver que si nos dan un número n, nuestra respuesta sería «Nn», donde N es todo 1.
Y podemos obtener n (que es la suma de todos los números enteros de A[i] a A[j]) usando “prefixSum[j] – prefixSum[i]”.
| Número (n) | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| Todos los 1 (N) | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Nn | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
C++
// CPP program to find smallest integer X
// such that sum of its XOR with range is
// maximum.
#include <bits/stdc++.h>
using namespace std;
// MAX is (1 << 31) -1 or in other terms 2^31 - 1
#define MAX 2147483647
int prefixSum[100001];
// Function to make prefix Sum array which
void make_prefix(int A[], int n)
{
prefixSum[0] = A[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + A[i];
}
// Function to find X
int Solve(int A[], int L, int R)
{
int n = prefixSum[R] - prefixSum[L] + A[L];
return MAX - n;
}
// Driver program
int main()
{
// Taking inputs
int n = 5, q = 3;
int A[] = { 210, 11, 48, 22, 133 };
int L[] = { 1, 4, 2 }, R[] = { 3, 4, 4 };
make_prefix(A, n);
for (int j = 0; j < q; j++)
cout << Solve(A, L[j], R[j]) << endl;
return 0;
}
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Gautam Karakoti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA