给定一个整数数组，我们需要得到所有子数组XOR的总XOR，其中子数组XOR可以通过对其所有元素进行XOR得到。 例如：
null
Input : arr[] = [3, 5, 2, 4, 6]Output : 7Total XOR of all subarray XORs is,(3) ^ (5) ^ (2) ^ (4) ^ (6)(3^5) ^ (5^2) ^ (2^4) ^ (4^6)(3^5^2) ^ (5^2^4) ^ (2^4^6)(3^5^2^4) ^ (5^2^4^6) ^(3^5^2^4^6) = 7 Input : arr[] = {1, 2, 3}Output : 2Input : arr[] = {1, 2, 3, 4}Output : 0
A. 简单解决方案 就是生成所有子数组并计算所有子数组的异或。以下是上述理念的实施情况：
C++
// C++ program to get total xor of all subarray xors #include <bits/stdc++.h> using namespace std; // Returns XOR of all subarray xors int getTotalXorOfSubarrayXors( int arr[], int N) { // initialize result by 0 as (a xor 0 = a) int res = 0; // select the starting element for ( int i=0; i<N; i++) // select the eNding element for ( int j=i; j<N; j++) // Do XOR of elements in current subarray for ( int k=i; k<=j; k++) res = res ^ arr[k]; return res; } // Driver code to test above methods int main() { int arr[] = {3, 5, 2, 4, 6}; int N = sizeof (arr) / sizeof (arr[0]); cout << getTotalXorOfSubarrayXors(arr, N); return 0; } |
JAVA
// java program to get total XOR // of all subarray xors public class GFG { // Returns XOR of all subarray xors static int getTotalXorOfSubarrayXors( int arr[], int N) { // initialize result by // 0 as (a xor 0 = a) int res = 0 ; // select the starting element for ( int i = 0 ; i < N; i++) // select the eNding element for ( int j = i; j < N; j++) // Do XOR of elements // in current subarray for ( int k = i; k <= j; k++) res = res ^ arr[k]; return res; } // Driver code public static void main(String args[]) { int arr[] = { 3 , 5 , 2 , 4 , 6 }; int N = arr.length; System.out.println( getTotalXorOfSubarrayXors(arr, N)); } } // This code is contributed by Sam007. |
Python 3
# python program to get total xor # of all subarray xors # Returns XOR of all subarray xors def getTotalXorOfSubarrayXors(arr, N): # initialize result by 0 as # (a xor 0 = a) res = 0 # select the starting element for i in range ( 0 , N): # select the eNding element for j in range (i, N): # Do XOR of elements in # current subarray for k in range (i, j + 1 ): res = res ^ arr[k] return res # Driver code to test above methods arr = [ 3 , 5 , 2 , 4 , 6 ] N = len (arr) print (getTotalXorOfSubarrayXors(arr, N)) # This code is contributed by Sam007. |
C#
// C# program to get total XOR // of all subarray xors using System; class GFG { // Returns XOR of all subarray xors static int getTotalXorOfSubarrayXors( int []arr, int N) { // initialize result by // 0 as (a xor 0 = a) int res = 0; // select the starting element for ( int i = 0; i < N; i++) // select the eNding element for ( int j = i; j < N; j++) // Do XOR of elements // in current subarray for ( int k = i; k <= j; k++) res = res ^ arr[k]; return res; } // Driver Code static void Main() { int []arr = {3, 5, 2, 4, 6}; int N = arr.Length; Console.Write(getTotalXorOfSubarrayXors(arr, N)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to get total // xor of all subarray xors // Returns XOR of all subarray xors function getTotalXorOfSubarrayXors( $arr , $N ) { // initialize result by // 0 as (a xor 0 = a) $res = 0; // select the starting element for ( $i = 0; $i < $N ; $i ++) // select the eNding element for ( $j = $i ; $j < $N ; $j ++) // Do XOR of elements in // current subarray for ( $k = $i ; $k <= $j ; $k ++) $res = $res ^ $arr [ $k ]; return $res ; } // Driver code $arr = array (3, 5, 2, 4, 6); $N = sizeof( $arr ); echo getTotalXorOfSubarrayXors( $arr , $N ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // JavaScript program for the above approach // Returns XOR of all subarray xors function getTotalXorOfSubarrayXors( arr, N) { // initialize result by // 0 as (a xor 0 = a) let res = 0; // select the starting element for (let i = 0; i < N; i++) // select the eNding element for (let j = i; j < N; j++) // Do XOR of elements // in current subarray for (let k = i; k <= j; k++) res = res ^ arr[k]; return res; } // Driver Code // Both a[] and b[] must be of same size. let arr = [3, 5, 2, 4, 6]; let N = arr.length; document.write(getTotalXorOfSubarrayXors(arr, N)); // This code is contributed by code_hunt. </script> |
输出：
7
时间复杂度：O（N） 3. ) 一 有效解决方案 基于枚举所有子数组的思想，我们可以计算每个元素在所有子数组中出现的频率，如果元素的频率是奇数，那么它将包含在最终结果中，否则不会。
As in above example, 3 occurred 5 times,5 occurred 8 times,2 occurred 9 times,4 occurred 8 times,6 occurred 5 timesSo our final result will be xor of all elements which occurred odd number of timesi.e. 3^2^6 = 7From above occurrence pattern we can observe that number at i-th index will have (i + 1) * (N - i) frequency.
所以我们可以迭代所有元素一次，然后计算它们的频率，如果它是奇数，那么我们可以通过将其与结果进行XOR运算，将其包含在最终结果中。 解决方案的总时间复杂度为O（N）
C++
// C++ program to get total // xor of all subarray xors #include <bits/stdc++.h> using namespace std; // Returns XOR of all subarray xors int getTotalXorOfSubarrayXors( int arr[], int N) { // initialize result by 0 // as (a XOR 0 = a) int res = 0; // loop over all elements once for ( int i = 0; i < N; i++) { // get the frequency of // current element int freq = (i + 1) * (N - i); // Uncomment below line to print // the frequency of arr[i] // cout << arr[i] << " " << freq << endl; // if frequency is odd, then // include it in the result if (freq % 2 == 1) res = res ^ arr[i]; } // return the result return res; } // Driver Code int main() { int arr[] = {3, 5, 2, 4, 6}; int N = sizeof (arr) / sizeof (arr[0]); cout << getTotalXorOfSubarrayXors(arr, N); return 0; } |
JAVA
// java program to get total xor // of all subarray xors import java.io.*; public class GFG { // Returns XOR of all subarray // xors static int getTotalXorOfSubarrayXors( int arr[], int N) { // initialize result by 0 // as (a XOR 0 = a) int res = 0 ; // loop over all elements once for ( int i = 0 ; i < N; i++) { // get the frequency of // current element int freq = (i + 1 ) * (N - i); // Uncomment below line to print // the frequency of arr[i] // if frequency is odd, then // include it in the result if (freq % 2 == 1 ) res = res ^ arr[i]; } // return the result return res; } public static void main(String[] args) { int arr[] = { 3 , 5 , 2 , 4 , 6 }; int N = arr.length; System.out.println( getTotalXorOfSubarrayXors(arr, N)); } } // This code is contributed by Sam007. |
Python 3
# Python3 program to get total # xor of all subarray xors # Returns XOR of all # subarray xors def getTotalXorOfSubarrayXors(arr, N): # initialize result by 0 # as (a XOR 0 = a) res = 0 # loop over all elements once for i in range ( 0 , N): # get the frequency of # current element freq = (i + 1 ) * (N - i) # Uncomment below line to print # the frequency of arr[i] # if frequency is odd, then # include it in the result if (freq % 2 = = 1 ): res = res ^ arr[i] # return the result return res # Driver Code arr = [ 3 , 5 , 2 , 4 , 6 ] N = len (arr) print (getTotalXorOfSubarrayXors(arr, N)) # This code is contributed # by Smitha |
C#
// C# program to get total xor // of all subarray xors using System; class GFG { // Returns XOR of all subarray xors static int getTotalXorOfSubarrayXors( int []arr, int N) { // initialize result by 0 // as (a XOR 0 = a) int res = 0; // loop over all elements once for ( int i = 0; i < N; i++) { // get the frequency of // current element int freq = (i + 1) * (N - i); // Uncomment below line to print // the frequency of arr[i] // if frequency is odd, then // include it in the result if (freq % 2 == 1) res = res ^ arr[i]; } // return the result return res; } // Driver Code public static void Main() { int []arr = {3, 5, 2, 4, 6}; int N = arr.Length; Console.Write(getTotalXorOfSubarrayXors(arr, N)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to get total // xor of all subarray xors // Returns XOR of all subarray xors function getTotalXorOfSubarrayXors( $arr , $N ) { // initialize result by 0 // as (a XOR 0 = a) $res = 0; // loop over all elements once for ( $i = 0; $i < $N ; $i ++) { // get the frequency of // current element $freq = ( $i + 1) * ( $N - $i ); // if frequency is odd, then // include it in the result if ( $freq % 2 == 1) $res = $res ^ $arr [ $i ]; } // return the result return $res ; } // Driver Code $arr = array (3, 5, 2, 4, 6); $N = count ( $arr ); echo getTotalXorOfSubarrayXors( $arr , $N ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to get total // xor of all subarray xors // Returns XOR of all subarray xors function getTotalXorOfSubarrayXors(arr, N) { // initialize result by 0 // as (a XOR 0 = a) let res = 0; // loop over all elements once for (let i = 0; i < N; i++) { // get the frequency of // current element let freq = (i + 1) * (N - i); // Uncomment below line to print // the frequency of arr[i] // cout << arr[i] << " " << freq << endl; // if frequency is odd, then // include it in the result if (freq % 2 == 1) res = res ^ arr[i]; } // return the result return res; } // Driver Code let arr = [3, 5, 2, 4, 6]; let N = arr.length; document.write(getTotalXorOfSubarrayXors(arr, N)); </script> |
输出：
7
时间复杂性： O（N） 本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
