範囲の最大の奇数除数のXORに関するC++クエリ

N個の整数の配列と範囲のQ個のクエリが与えられます。クエリごとに、範囲内の各数値の最大の奇数除数のXORを返す必要があります。

最大の奇数除数は、数Nを除算できる最大の奇数です。たとえば、6の最大の奇数除数は3です。

Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
Output:
query1: 7
query2: 1

Explanation: greatest odd divisors of nums array are { 3, 3, 7, 5 }.
For query 1 we need to find the XOR of indexes 0, 1, and 2 which is 7, and for query2 we need to find XOR of indexes 1, 2, and 3 which is 1.

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

シンプルなアプローチ

まず、単純なアプローチでは、すべての配列要素の中で最大の奇数除数を見つける必要があります。次に、クエリの範囲に応じて、範囲内の各要素のXORを計算して返す必要があります。

効率的なアプローチ

この問題を解決する効率的な方法は、範囲内の各数値のXORを見つけるたびに、prefix_XOR [R] --prefix_XOR [L-1を返すのではなく、最大の奇数除数を含む配列のプレフィックスXOR配列prefix_XOR[]を作成することです。 ]。

プレフィックスxor配列は、各要素に前のすべての要素のxorが含まれる配列です。

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = { 3, 6, 7, 10 };
    int n = sizeof(nums) / sizeof(nums[0]);
    int prefix_XOR[n];
    // creating an array
    // containing Greatest odd divisor of each element.
    for (int i = 0; i < n; i++) {
        while (nums[i] % 2 != 1)
            nums[i] /= 2;
        prefix_XOR[i] = nums[i];
    }
    // changing prefix_XOR array to prefix xor array.
    for (int i = 1; i < n; i++)
        prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
    // query array to find result of these queries.
    int query[2][2] = {{0, 2},{1, 3}};
    int q = sizeof(query) / sizeof(query[0]);
    // finding results of queries.
    for(int i = 0;i<q;i++){
        if (query[i][0] == 0)
            cout<<  prefix_XOR[query[i][1]] << endl;
        else{
            int result = prefix_XOR[query[0][1]] ^ prefix_XOR[query[i][0] - 1];
            cout <<  result << endl;
        }
    }
    return 0;
}

出力

7
4

上記のコードの説明

• prefix_XOR配列は、各要素の最大の奇数除数を格納し、この配列をプレフィックスXOR配列に変更するために作成されます。

• 最大の奇数除数は、モジュロ2が1になるまで2で割ることによって計算されます。

• プレフィックスxor配列は、配列をトラバースし、現在の要素と前の要素のビット単位のXORを実行することによって作成されます。

• クエリの結果は、prefix_XOR []配列の右側のインデックスとprefix_XOR[]配列の（左側-1）インデックスを減算することによって計算されます。

結論

このチュートリアルでは、指定された配列の範囲内の各数値の最大の奇数除数のXORを見つける必要がある問題について説明しました。各要素の最大の奇数除数を見つけ、接頭辞xor配列を使用することにより、この問題を解決するアプローチについて説明しました。また、C、Java、Pythonなどのプログラミング言語で実行できるこの問題のC++プログラムについても説明しました。この記事がお役に立てば幸いです。