Tổng XOR của tổng 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 [] có kích thước 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ổng của tất cả các cặp trong một mảng.

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

Đầu vào: arr [5, 7, 9]

Đầu ra: 22

Giải thích:

(5 + 5) ^ (5 + 7) ^ (5 + 9) ^ (7 + 5) ^ (7 + 7) ^ (7 + 9) ^ (9 + 5) ^ (9 + 7) ^ (9 + 9) =22

Một giải pháp đơn giản cho vấn đề là sử dụng một vòng lặp lồng nhau. Và tạo tất cả các cặp có thể có từ mảng. Và tính XOR của tổng của mỗi cặp.

Thuật toán:

Khởi tạo XorSum =0

Bước 1: lặp từ 0 đến n. Theo:

Bước 1.1: lặp từ 0 đến n. Theo dõi

Bước 1.1.1: Cập nhật XorSum tức là XorSum =XorSum ^ (arr [i] + arr [j]).

Bước 2: trả lại số tiền

Chương trình minh họa hoạt động của mã của chúng tôi

Ví dụ

#include <iostream>
using namespace std;

int findSumXORPair(int arr[], int n) {

   int XorSum = 0;
   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
       XorSum = XorSum^(arr[i]+arr[j]);
   return XorSum;
}

int main() {

   int arr[] = {5, 7, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
   return 0;
}

Đầu ra

XOR of sum of all pairs in an array is 22

Giải pháp này không hiệu quả vì độ phức tạp về thời gian của nó là n ² .

Một giải pháp hiệu quả là sử dụng các thuộc tính của XOR. Để giải quyết vấn đề, chúng tôi sẽ tính XOR của tất cả các phần tử của mảng và sau đó nhân nó với hai.

Thuật toán:

Khởi tạo XorSum =0

Bước 1: Lặp lại từ 0 đến n.

Bước 1.1: cập nhật XorSum tức là XorSum =XorSum ^ arr [i]

Bước 2: nhân đôi tổng và trả lại.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <iostream>
using namespace std;

int findSumXORPair(int arr[], int n) {

   int XorSum = 0;
   for (int i = 0; i < n; i++)
    XorSum = XorSum^arr[i];
   XorSum = 2*XorSum;
   return XorSum;
}

int main() {

int arr[] = {5, 7, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
   return 0;
}

Đầu ra

XOR of sum of all pairs in an array is 22