배열과 일부 쿼리가 제공되는 문제를 해결하기 위해. 이제 각 쿼리에서 범위가 제공됩니다. 이제 x와 xor의 합이 최대화되는 숫자를 찾아야 합니다. 예를 들면
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645 이 문제에서 우리는 1의 수를 미리 계산했기 때문에 각 위치의 숫자에 존재하는 1의 접두사 카운트를 취할 것이므로 L에서 R까지 주어진 범위에서 1의 수를 찾으려면 다음을 수행해야 합니다. L까지 추정하고 R까지 추정을 뺍니다.
해결책을 찾기 위한 접근 방식
이 접근 방식에서는 최대 합을 찾아야 하므로 xor 비트의 대부분을 1로 만들어야 합니다. 따라서 우리는 하나가 0의 수보다 많은 경우 비트를 확인하므로 이제 대부분의 숫자가 해당 비트를 1로 지정하므로 x의 해당 비트를 재설정하므로 대다수 1을 0과 짝지을 때 결국 대부분의 그 비트는 1이므로 이것이 우리가 답을 최대화하는 방법입니다.
예시
위 접근 방식에 대한 C++ 코드
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // the prefix array
void prefix_bit(int A[], int n){ // taking prefix count of 1's present
for (int j = 0; j < 32; j++) // we keep 0th count as 0 and our prefix array starts with index 1
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // making our prefix array
int a = A[i - 1]; // ith element
for (int j = 0; j < 32; j++){ // as our number is less than 2^32 so we traverse for bit 0 to 31
int x = 1 << j; // traversing in bits
if (a & x) // if this bit is one so we make the prefix count as prevcount + 1
prefix[i][j] = 1 + prefix[i - 1][j];
else
prefix[i][j] = prefix[i - 1][j];
}
}
}
int maximum_num(int l, int r){
int numberofbits = r - l + 1; // the number of elements in the range hence the number of bits
int X = MAX; // we take the max value such that all of it's bits are one
// Iterating over each bit
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // calculating the number of set bits in the given range
if (x >= numberofbits - x){ // is number of 1's is more than number of 0's
int currentbit = 1 << i; // we set the current bit to prefix for toggling that bit in x
X = X ^ currentbit; // we make toggle that bit from 1 to 0
}
}
return X; // answer
}
int main(){
int n = 5, q = 3; // number of element in our array and number of queries present
int A[] = { 210, 11, 48, 22, 133 }; // elements in our array
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // given queries
prefix_bit(A, n); // creating prefix bit array
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
} 출력
2147483629 2147483647 2147483629
위 코드 설명
이 접근 방식에서는 먼저 각 비트에 대해 존재하는 1의 접두사 수를 계산합니다. 이제 이 개수를 얻었을 때 쿼리를 순회하는 가장 큰 문제를 해결했습니다. 현재로서는 각 범위를 순회하지 않습니다. 이제 접두사 배열을 통해 계산할 수 있습니다. 우리의 주요 논리는 세트 비트 수가 리셋 비트 수보다 많은 위치를 만났을 때 범위에서 리셋 및 세트 비트 수를 계산한다는 것입니다. 따라서 2^31 - 1로 x를 초기화했으므로 이제 x의 해당 비트를 재설정하여 모든 비트가 설정되고 x의 비트를 토글하여 답을 찾습니다.
결론
이 튜토리얼에서는 주어진 배열 범위에 대한 XOR의 합이 최대인 숫자를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.