Tổng XOR của tất cả các cặp trong một mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số nguyên. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tổng XOR của tất cả các cặp trong một mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Một cách đơn giản để giải quyết vấn đề này là chạy các vòng lặp lồng nhau và tìm tất cả các cặp số. Tìm XOR của từng cặp và cộng chúng thành tổng.

Thuật toán

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.

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>
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;
}

Đầu ra

Sum of XOR of all pairs in an array is 10

Độ phức tạp về thời gian của thuật toán là O (n2) và không phải là giải pháp hiệu quả nhất cho vấn đề.

Một giải pháp hiệu quả cho vấn đề là sử dụng kỹ thuật thao tác bit.

Ở đây, chúng ta sẽ xem xét các bit của số và tại mỗi vị trí. Và áp dụng công thức dưới đây để tìm tổng trung gian,

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

Để tìm tổng cuối cùng, chúng tôi sẽ cộng tổng trung gian của tất cả các bit.

Giải pháp của chúng tôi là dành cho giá trị số nguyên 64 bit. Đối với cách tiếp cận này, chúng tôi cần số lượng bit.

Thuật toán

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))

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;
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;
}

Đầu ra

Sum of XOR of all pairs in an array is 68