ผลรวมของ XOR ของคู่ทั้งหมดในอาร์เรย์ใน C++

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

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

Input: arr[] = {5, 1, 4}
Output: 10
Explanation: the sum of all pairs:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
sum = 4 + 5 + 1 = 10

วิธีง่ายๆ วิธีหนึ่งในการแก้ปัญหานี้คือเรียกใช้การวนซ้ำแบบซ้อนและค้นหาคู่ของตัวเลขทั้งหมด ค้นหา XOR ของแต่ละคู่และเพิ่มลงในผลรวม

อัลกอริทึม

Initialise sum = 0
Step 1: for(i -> 0 to n). Do:
   Step 1.1: for( j -> i to n ). Do:
      Step 1.1.1: update sum. i.e. sum += arr[i] ^ arr[j].
Step 2: return sum.

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
    sum += (arr[i]^arr[j]);
   return sum;
}
int main() {
   int arr[] = { 5, 1, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
   return 0;
}

ผลลัพธ์

Sum of XOR of all pairs in an array is 10

ความซับซ้อนของเวลาของอัลกอริทึมคือ O(n2) และไม่ใช่วิธีแก้ปัญหาที่มีประสิทธิภาพที่สุด

วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้เทคนิคการจัดการบิต

ในที่นี้ เราจะพิจารณาบิตของตัวเลขและในแต่ละตำแหน่ง และใช้สูตรด้านล่างหาผลรวมกลาง

(number of set bits) * (number of unset bits) * (2^(bit_position))

เพื่อหาผลรวมสุดท้าย เราจะบวกผลรวมกลางของบิตทั้งหมด

โซลูชันของเราใช้สำหรับค่าจำนวนเต็ม 64 บิต สำหรับวิธีนี้ เราต้องการจำนวนบิต

อัลกอริทึม

Initialize sum = 0, setBits = 0, unsetBits = 0.
Step 1: Loop for i -> 0 to 64. repeat steps 2, 3.
Step 2: Reset setBits and unsetBits to 0.
Step 3: For each element of the array find the value of setBits and unsetBits. At ith position.
Step 4: update sum += (setBits * unsetBits * (2i))

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
   long sum = 0;
   int unsetBits = 0, setBits = 0;
   for (int i = 0; i < 32; i++) {
      unsetBits = 0; setBits = 0;
      for (int j = 0; j < n; j++) {
         if (arr[j] % 2 == 0)
            unsetBits++;
         else
            setBits++;
         arr[j] /= 2;
      }
      sum += ( unsetBits*setBits* (pow(2,i)) );
   }
   return sum;
}
int main() {
   int arr[] = { 5, 1, 4, 7, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
   return 0;
}

ผลลัพธ์

Sum of XOR of all pairs in an array is 68