使用 C++ 查找与给定数组范围异或和最大的数字

要解决一个问题，其中给定一个数组和一些查询。现在在每个查询中，给定一个范围。现在我们需要找到一个数字，使得它与 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 的数量。

查找解决方案的方法

在这种方法中，因为我们需要找到最大和，所以我们需要使异或的大多数位等于 1；因此，我们检查对于任何位，如果 1 的数量大于 0 的数量，那么我们将 x 的该位置重置为 0，因为现在大多数数字的该位等于 1，所以当我们将这些大多数的 1 与 0 配对时，最终我们将使该位的大多数等于 1，因此这就是我们最大化答案的方法。

示例

上述方法的 C++ 代码

Open Compiler
#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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

2147483629
2147483647
2147483629

上述代码的解释

在这种方法中，我们首先计算每一位存在的 1 的前缀计数。现在，当我们得到这个计数时，我们就解决了我们最大的问题，即遍历查询。从现在开始，我们将不会遍历每个范围。因此，我们可以通过我们的前缀数组来计算。我们的主要逻辑是，当我们遇到一个 1 的数量大于 0 的数量的位置时，我们计算该范围内重置位和设置位的数量。因此，我们现在在 x 中重置该位，因为我们已将 x 初始化为 2^31 - 1，所以它的所有位都将被设置，并且我们通过切换 x 中的位来找到我们的答案。

结论

在本教程中，我们解决了一个问题，即查找与给定数组范围异或和最大的数字。我们还学习了此问题的 C++ 程序以及我们解决此问题的完整方法（常规）。我们可以用其他语言（如 C、Java、Python 和其他语言）编写相同的程序。我们希望您觉得本教程有所帮助。

更新于： 2021 年 11 月 25 日

214 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告