Pertanyaan XOR untuk pembahagi ganjil maksimum dalam julat dalam C++

Diberi tatasusunan yang mengandungi N integer dan pertanyaan julat Q. Untuk setiap pertanyaan, kita perlu mengembalikan XOR pembahagi ganjil terbesar bagi setiap nombor dalam julat.

Pembahagi ganjil terbesar ialah nombor ganjil terbesar yang boleh membahagi nombor N, seperti . Sebagai contoh, pembahagi ganjil terbesar bagi 6 ialah 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.

Kaedah penyelesaian

Kaedah ringkas

Pertama, dalam kaedah mudah, kita perlu mencari pembahagi ganjil terbesar bagi semua elemen tatasusunan. Kemudian berdasarkan julat pertanyaan, kita perlu mengira XOR setiap elemen dalam julat dan mengembalikannya.

Kaedah berkesan

Cara yang berkesan untuk menyelesaikan masalah ini ialah dengan mencipta awalan tatasusunan XOR awalan_XOR[] yang mengandungi tatasusunan dengan pembahagi ganjil terbesar, bukannya memasangkan julat setiap satu masa XOR setiap nombor dan mengembalikan prefix_XOR[R] - prefix_XOR[L-1].

Awalan tatasusunan XOR ialah tatasusunan di mana setiap elemen mengandungi XOR semua elemen sebelumnya.

Contoh

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

Output

7
4

Perihalan kod di atas

#🎜🎜🎜#🎜🎜🎜🎜🎜🎜#

• #🎜✎ tatasusunan untuk menyimpan pembahagi ganjil terbesar bagi setiap elemen, kemudian tukar tatasusunan ini kepada tatasusunan XOR awalan.

• Pembahagi ganjil terbesar dikira dengan membahagikannya dengan dua sehingga modulo 2 anda mendapat 1.

• Cipta tatasusunan XOR awalan dengan merentasi tatasusunan dan lakukan XOR bitwise bagi elemen semasa dengan elemen sebelumnya.

• Hasil pertanyaan dikira dengan menolak indeks kanan tatasusunan awalan_XOR[] (kiri - 1) Indeks tatasusunan prefix_XOR[].

Kesimpulan

Dalam tutorial ini, kami membincangkan masalah di mana kami perlu mencari nombor ganjil maksimum XOR bagi setiap nombor dalam julat pembahagi tatasusunan yang diberikan. Kami membincangkan cara untuk menyelesaikan masalah ini dengan mencari pembahagi ganjil terbesar untuk setiap elemen dan menggunakan tatasusunan XOR awalan. Kami juga membincangkan program C++ untuk masalah ini dan kami boleh melakukannya menggunakan bahasa pengaturcaraan seperti C, Java, Python dll. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Pertanyaan XOR untuk pembahagi ganjil maksimum dalam julat dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!