C++ の範囲内の最大奇数除数を求める XOR クエリ

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[] を作成することです。 XOR を計算し、prefix_XOR[R] - prefix_XOR[L-1] を返します。

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

例

#include  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
        

         ログイン後にコピー
        
       

出力

7 4

上記のコードの説明

• prefix_XOR配列を作成して、次の最大の奇数を格納します。次に、この配列をプレフィックス XOR 配列に変更します。

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

• 配列を走査し、現在の要素と前の要素のビット単位の XOR を実行することにより、プレフィックス XOR 配列を作成します。

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

#結論

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

以上がC++ の範囲内の最大奇数除数を求める XOR クエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。