ผลรวมของ XOR ของชุดย่อยที่เป็นไปได้ทั้งหมดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ aar[] ของ n ตัวเลข งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของ XOR ของชุดย่อยที่เป็นไปได้ทั้งหมด

ที่นี่ เราจะพบชุดย่อยทั้งหมดของอาร์เรย์ จากนั้นสำหรับแต่ละเซ็ตย่อย เราจะหา XOR ขององค์ประกอบของเซ็ตย่อยและเพิ่มเข้าไปในตัวแปรผลรวม

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

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

วิธีแก้ปัญหาอย่างง่ายคือใช้ลูปและค้นหาชุดย่อยที่เป็นไปได้ทั้งหมดของอาร์เรย์ จากนั้นสำหรับแต่ละชุดย่อยให้ค้นหา XOR ขององค์ประกอบทั้งหมดและอัปเดตผลรวม คืนผลรวมในตอนท้าย

นี่ไม่ใช่แนวทางที่มีประสิทธิภาพ สำหรับความซับซ้อนของเวลาที่เพิ่มขึ้นอย่างมากสำหรับมูลค่าที่มาก ความซับซ้อนของเวลาจะเพิ่มขึ้นแบบทวีคูณ

วิธีที่มีประสิทธิภาพคือการใช้คุณสมบัติของ XOR ที่นี่ เราจะพบ OR ขององค์ประกอบทั้งหมดของอาร์เรย์ และตรวจสอบบิต หากตั้งค่า ith แล้ว ให้อัปเดตผลรวมด้วย (2^(n-1+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);
}

ผลลัพธ์

Sum of XOR of all possible subsets is 20