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

이 문제에서는 n개의 정수로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 배열에 있는 모든 쌍의 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