ผลรวมของ XOR ของทุกซับเซ็ตที่เป็นไปได้ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n งานคือหาผลรวมของ XOR ของทุกซับเซ็ต (ทุกชุดย่อย) ที่เป็นไปได้ของอาร์เรย์

ตัวอย่าง

Input: arr[] = {5, 1, 4}
Output: 20
Explanation:
XOR ของทุกซับเซ็ต:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
ผลรวม XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20

วิธีแก้ปัญหา

วิธีง่าย

วนลูปหาซับเซ็ตทั้งหมด คำนวณ XOR แต่ละเซ็ต และบวกสะสม

ข้อเสีย: ความซับซ้อนเวลาแบบเอ็กซ์โพเนนเชียล

วิธีที่มีประสิทธิภาพ (ใช้คุณสมบัติ XOR)

หา OR ของทุกอิลิเมนต์ในอาร์เรย์ ตรวจสอบบิตแต่ละตำแหน่ง หากบิตที่ i เป็น 1 ให้อัปเดตผลรวมด้วย (2^(n-1+i))

เหตุผล: แต่ละบิตจะมีส่วนร่วมในผลรวม XOR ของซับเซ็ตทั้งหมดเท่ากัน

ตัวอย่างโค้ด C++

#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);
    return 0;
}

ผลลัพธ์

Sum of XOR of all possible subsets is 20