Trong bài toán này, chúng ta được đưa ra một mảng aar [] gồm n số. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Tổng XOR của tất cả các tập hợp con có thể có.
Tại đây, chúng ta sẽ tìm thấy tất cả các tập con của mảng. Sau đó, đối với mỗi tập hợp con, chúng tôi sẽ tìm XOR của các phần tử của tập hợp con và thêm chúng vào biến tổng.
Hãy lấy một ví dụ để hiểu vấn đề,
Input: arr[] = {5, 1, 4}
Output: 20
Explanation: XOR of all subsets:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Sum of XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20 Một giải pháp đơn giản cho vấn đề là sử dụng vòng lặp và tìm tất cả các tập con có thể có của mảng và sau đó đối với mỗi tập con, hãy tìm XOR của tất cả các phần tử và cập nhật tổng. Trả lại số tiền khi kết thúc.
Đây không phải là một cách tiếp cận hiệu quả, đối với giá trị lớn, độ phức tạp về thời gian sẽ tăng lên theo cấp số nhân.
Một cách tiếp cận hiệu quả là sử dụng các thuộc tính của XOR. Ở đây, chúng ta sẽ tìm OR của tất cả các phần tử của mảng và kiểm tra các bit. Nếu thứ i được đặt, thì hãy cập nhật tổng bằng (2 ^ (n-1 + i)).
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <iostream>
#include <math.h>
using namespace std;
int subSetXORSum(int arr[], int n) {
int bitOR = 0;
for (int i=0; i < n; ++i)
bitOR |= arr[i];
return (bitOR * pow(2, n-1));
}
int main() {
int arr[] = {1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all possible subsets is "<<subSetXORSum(arr, size);
} Đầu ra
Sum of XOR of all possible subsets is 20