資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中所有子陣列 XOR 的異或
在這個問題中，我們給定一個包含 n 個元素的陣列。我們的任務是列印從陣列元素建立的所有可能的子陣列（按順序取）的 XOR 的異或。
讓我們舉一個例子來理解這個問題，
輸入 - 陣列 = {1, 3, 6, 8}
輸出 - 0
解釋 -
(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6)^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)
為了解決這個問題，一個簡單的解決方案可能是遍歷所有子陣列並找到異或。但這是一種低效的方法。更好的方法可能是計算陣列中每個元素在所有子陣列中出現的頻率，並使用異或的性質 - *元素異或偶數次的結果為 0*。利用這一點，我們將忽略在子陣列列表中出現偶數次的的所有值，現在需要考慮出現頻率為奇數的元素，即出現頻率為奇數的元素的異或將給出最終結果。
為了找到陣列中每個元素在其子陣列中的出現次數，我們將使用此公式 (i+1)*(n-i)。
使用此公式，我們將找到每個元素出現的頻率，然後考慮那些具有奇數頻率的元素，異或它們以獲得最終結果。
示例
程式展示了我們解決方案的實現，
#include <iostream>
using namespace std;
int xorSubarrayXors(int arr[], int N){
int result = 0;
for (int i = 0; i < N; i++){
int freqency = (i + 1) * (N - i);
if (freqency % 2 == 1)
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {1, 3, 6, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The xor of all subarray xors is : "<<xorSubarrayXors(arr, N);
return 0;
}輸出
The xor of all subarray xors is : 0
更新於: 2020年4月20日
392 次檢視
廣告