이 문제에서는 n 요소의 배열이 제공됩니다. 우리의 임무는 배열의 요소에서 생성된 모든 가능한 하위 배열(순서대로 취함)의 XOR을 XOR로 인쇄하는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - 배열 ={1, 3, 6, 8}
출력 - 0
설명 -
(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6)^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)
이 문제를 해결하기 위해 간단한 솔루션은 모든 하위 배열을 반복하고 xor를 찾는 것입니다. 그러나 이것은 비효율적인 접근 방식입니다. 더 나은 접근 방식은 모든 하위 배열에서 발생한 배열의 각 요소 빈도를 계산하고 xor - 요소의 xor 짝수 횟수가 0 속성을 사용하는 것입니다. . 이것을 사용하여 우리는 하위 배열 목록에서 짝수 번 발생하는 모든 값을 무시할 것입니다. 이제 홀수 발생 빈도를 가진 요소가 고려됩니다. 즉, 홀수 발생 빈도를 가진 요소의 xor가 최종 결과를 제공합니다.
하위 배열에서 배열의 각 요소 발생을 찾기 위해 다음 공식을 사용합니다. (i+1)*(n-i) .
이 공식을 사용하여 각 요소의 발생 빈도를 찾은 다음 홀수 빈도를 갖는 요소를 고려하고 xor를 사용하여 최종 결과를 얻습니다.
예시
솔루션 구현을 보여주는 프로그램,
#include <iostream>
using namespace std;
int xorSubarrayXors(int arr[], int N){
int result = 0;
for (int i = 0; i < N; i++){
int freqency = (i + 1) * (N - i);
if (freqency % 2 == 1)
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {1, 3, 6, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The xor of all subarray xors is : "<<xorSubarrayXors(arr, N);
return 0;
} 출력
The xor of all subarray xors is : 0