XOR-Abfrage für den maximalen ungeraden Teiler im Bereich in C++

Gegeben sei ein Array mit N Ganzzahlen und Q-Bereichsabfragen. Für jede Abfrage müssen wir das XOR des größten ungeraden Teilers jeder Zahl im Bereich zurückgeben.

Der größte ungerade Teiler ist die größte ungerade Zahl, die die Zahl N teilen kann, wie zum Beispiel . Beispielsweise ist der größte ungerade Teiler von 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.

So lösen Sie

Einfache Methode

Zuerst müssen wir bei der einfachen Methode den größten ungeraden Teiler aller Array-Elemente finden. Dann müssen wir basierend auf dem Bereich der Abfrage das XOR jedes Elements im Bereich berechnen und zurückgeben.

Effizienter Ansatz

Eine effiziente Möglichkeit, dieses Problem zu lösen, besteht darin, ein Präfix-XOR-Array prefix_XOR[] zu erstellen, das das Array mit dem größten ungeraden Teiler enthält, anstatt jede Zahl im Bereich jedes Mal per XOR zu verknüpfen und prefix_XOR[R ] - prefix_XOR zurückzugeben [L-1].

Präfix-XOR-Array ist ein Array, bei dem jedes Element das XOR aller vorherigen Elemente enthält.

Beispiel

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

Ausgabe

7
4

Obenige Codebeschreibung

• Erstellen Sie ein prefix_XOR-Array, um den größten ungeraden Teiler jedes Elements zu speichern, und ändern Sie dieses Array dann in ein Präfix-XOR-Array.

• Der größte ungerade Teiler wird berechnet, indem man ihn durch zwei dividiert, bis Modulo 2 1 ergibt.

• Erstellen Sie ein Präfix-XOR-Array, indem Sie das Array durchlaufen und eine bitweise XOR-Verknüpfung des aktuellen Elements mit dem vorherigen Element durchführen.

• Das Abfrageergebnis wird berechnet, indem der rechte Index des prefix_XOR[]-Arrays (links - 1) vom Index des prefix_XOR[]-Arrays subtrahiert wird.

Fazit

In diesem Tutorial haben wir ein Problem besprochen, bei dem wir den größten ungeraden Teiler für jede Zahl im Bereich eines bestimmten Arrays XOR finden müssen. Wir haben eine Möglichkeit diskutiert, dieses Problem zu lösen, indem wir den größten ungeraden Teiler für jedes Element finden und ein Präfix-XOR-Array verwenden. Wir haben auch ein C++-Programm für dieses Problem besprochen und können dies mit Programmiersprachen wie C, Java, Python usw. tun. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonXOR-Abfrage für den maximalen ungeraden Teiler im Bereich in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!