C ++を使用して、指定された配列範囲のXORの合計が最大になる数を見つけます

配列といくつかのクエリが与えられる問題を解決するため。各クエリで、範囲が指定されます。ここで、たとえば、xorとxの合計が最大になるような数を見つける必要があります

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の数を見つけるには、次のことを行う必要があります。 Rまでの推定値をLまでの推定値から減算します。

解決策を見つけるためのアプローチ

このアプローチでは、最大の合計を見つける必要があるため、xorのビットの大部分を1に等しくする必要があります。したがって、ビットが0の数よりも大きいかどうかを確認し、xのビットをリセットします。これは、数値の大部分が1に等しいビットであるため、その大部分の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のプレフィックスカウントを計算します。このカウントを取得すると、クエリをトラバースすることであった最大の問題が解決されました。現在のところ、各範囲をトラバースすることはありません。これで、プレフィックス配列を使用してそれを計算できます。私たちの主な論理は、セットビット数がリセットビット数よりも多い位置に遭遇したときに、範囲内のリセット数とセットビット数を計算することです。したがって、xを2 ^ 31-1で初期化したので、xのそのビットをリセットして、すべてのビットを設定し、xのビットを切り替えることで答えを見つけます。

結論

このチュートリアルでは、問題を解決して、特定の配列範囲でのXORの合計が最大になる数を見つけます。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。