C++의 배열에 있는 모든 쌍의 합에 대한 XOR의 합

이 문제에서는 크기가 n인 배열 arr[]이 제공됩니다. 우리의 임무는 배열에 있는 모든 쌍의 합계의 XOR 합계를 찾는 프로그램을 만드는 것입니다.

문제를 이해하기 위한 예를 살펴보겠습니다.

입력: arr[5, 7, 9]

출력: 22

설명:

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

문제에 대한 간단한 해결책은 중첩 루프를 사용하는 것입니다. 그리고 배열에서 가능한 모든 쌍을 만듭니다. 그리고 각 쌍의 합에 대한 XOR을 계산합니다.

알고리즘:

XorSum 초기화 =0

1단계: 0에서 n까지 반복합니다. 팔로우:

1.1단계: 0에서 n까지 반복합니다. 팔로우

1.1.1단계: XorSum 업데이트 즉, XorSum =XorSum ^ (arr[i]+arr[j]).

2단계: 반환 합계

코드의 작동을 설명하는 프로그램

예시

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

출력

XOR of sum of all pairs in an array is 22

이 솔루션은 시간 복잡도가 n ² 이므로 효율적이지 않습니다. .

효율적인 솔루션은 XOR의 속성을 사용하는 것입니다. 문제를 해결하기 위해 배열의 모든 요소에 대한 XOR을 계산한 다음 2를 곱합니다.

알고리즘:

XorSum =0

1단계: 0에서 n까지 반복합니다.

1.1단계: XorSum 업데이트 즉, XorSum =XorSum ^ arr[i]

2단계: 합계를 두 배로 하여 반환합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

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

출력

XOR of sum of all pairs in an array is 22