給定數組范圍的 XOR 之和最大的數字 · GeeksForGeeks 中文系列教程

# 給定數組范圍的 XOR 之和最大的數字 > 原文： [https://www.geeksforgeeks.org/number-whose-sum-of-xor-with-given-array-range-is-maximum/](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 // 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 // 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 ```py # 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# ```cs // 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 <?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 ``` * * * * * *