資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中所有子陣列的異或和
在這個問題中，我們給定一個包含 n 個數字的陣列 arr[]。我們的任務是建立一個程式來找到陣列所有子陣列的異或和。
這裡，我們需要找到給定陣列的所有子陣列，然後對於每個子陣列，我們將找到元素的異或並將其新增到 sum 變數中。
讓我們舉個例子來理解這個問題，
Input: arr[] = {5, 1, 4}
Output:
Explanation: XOR of all subarrays for the array :
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
Sum = 5 + 1 + 4 + 4 + 5 + 0 = 19解決此問題的一個簡單方法是使用下一個 for 迴圈來查詢所有子陣列。然後找到子陣列元素的異或並將其新增到 sum 變數中。
此解決方案效率不高，因為它使用了迴圈巢狀並且將具有指數時間複雜度。
解決此問題的一個有效方法是使用字首陣列。此字首陣列將儲存陣列中所有元素到 i 的異或。即，
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].
之後，我們可以應用一個簡單的公式來查詢從索引 i 到 j 的元素的異或。
XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0. If i = 0, XOR(i-j) = prefixarr[j]
使用此公式，我們將找到所有子陣列的異或。
示例
程式說明我們解決方案的工作原理，
#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
int sum = 0;
int multiplier = 1;
for (int i = 0; i < 30; i++) {
int oddCount = 0;
bool isOdd = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
isOdd = (!isOdd);
if (isOdd)
oddCount++;
}
for (int j = 0; j < n; j++) {
sum += (multiplier * oddCount);
if ((arr[j] & (1 << i)) > 0)
oddCount = (n - j - oddCount);
}
multiplier *= 2;
}
return sum;
}
int main() {
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all subarrays is "<<calcSubArrayXORSum(arr, n);
return 0;
}輸出
Sum of XOR of all subarrays is 46
更新於: 2020-08-17
755 次瀏覽
廣告