C++에서 부분배열의 XOR

이 문제에서는 arr[]과 배열에서 L에서 R 사이의 범위에 있는 일부 쿼리가 제공됩니다. 우리의 임무는 L에서 R 사이의 하위 배열의 XOR을 인쇄하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={1, 4, 5, 7, 2, 9} L =1, R =5

출력 -

설명 − 4^5^7^2^9

• 이 문제를 해결하기 위해 다음 관찰을 기반으로 배열을 만듭니다.

• 여러 비트를 XOR합니다. 1이 홀수이면 결과는 1이 되고 그렇지 않으면 결과는 0이 됩니다.

이제 1의 개수를 저장할 2차원 배열 개수를 생성합니다. count[i][j] 값은 비트의 i번째 위치에 있는 하위 배열 arr[0..j]에 있는 1의 개수인 위치 i-j에 대한 1의 개수입니다. 하위 배열 arr[L..R]의 모든 비트에 대한 1의 수는 count 배열을 사용하여 찾습니다. arr[L...R]을 구하는 공식 =count[i][R] - count[i][L-1]. 1의 개수가 홀수이면 i번째 비트가 결과에 설정됩니다. i번째 비트가 설정되어 있는 비트에 해당하는 2의 거듭제곱을 합산하면 최종 결과를 얻을 수 있습니다.

솔루션 구현을 보여주는 프로그램,

예

#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
   int i, j;
   for (i = 0; i < 32; i++) {
      cnt[i][0] = 0;
      for (j = 0; j < n; j++) {
         if (j > 0) {
            cnt[i][j] = cnt[i][j - 1];
         }
         if (arr[j] & (1 << i))
         cnt[i][j]++;
      }
   }
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
   int result = 0;
   int noOfOnes;
   int i, j;
   for (i = 0; i < 32; i++) {
      noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
      if (noOfOnes & 1) {
         result+=(1 << i);
      }
   }
   return result;
}
int main(){
   int arr[] = { 1, 4, 5, 7, 2, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   vector<vector<int> > count(32, vector<int>(n));
   preProcessArray(arr, n, count);
   int L = 1;
   int R = 5;
   cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
   return 0;
}

출력

The XOR of SubArray: 13