给定数组范围的 XOR 与它之和最大的数字
原文： https://www.geeksforgeeks.org/number-whose-sum-of-xor-with-given-array-range-is-maximum/
系统会为您提供N个整数和Q个查询的序列。 在每个查询中，给您两个参数L和R。您必须找到最小的整数X，使得0 <= X < 2 ^ 31，并且x与范围[L, R]的所有元素的 XOR 之和是最大可能的。
示例：
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645
方法：每个元素和x的二进制表示，我们可以观察到每个位都是独立的，并且可以通过迭代每个位来解决问题。 现在基本上，对于每个位，我们都需要计算给定范围内的 1 和 0 的数量，如果 1 的数量更多，则必须将x的该位设置为 0，以便在x或x之后用x取最大，否则 0 的数量更多，那么您必须将x的该位设置为 1。如果 1 和 0 的数量相等，那么我们可以将x的该位设置为 1 或 0 中的任何一个，因为这不会影响总和，但是我们必须最小化x的值，因此我们将使用该位 0。
现在，为了优化解决方案，我们可以通过创建前缀数组来预先计算数字的每个位位置上的 1 的计数，这将花费O(n)时间。 现在，对于每个查询，从 1 到第R个位置的数字都是 1，由 1 到第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)
?>
输出：
2147483629
2147483647
2147483629
版权属于：月萌API www.moonapi.com，转载请注明出处
