Requête XOR pour le diviseur impair maximum dans la plage en C++

Étant donné un tableau contenant N entiers et des requêtes de plage Q. Pour chaque requête, nous devons renvoyer le XOR du plus grand diviseur impair de chaque nombre de la plage.

Le plus grand diviseur impair est le plus grand nombre impair pouvant diviser le nombre N, tel que . Par exemple, le plus grand diviseur impair de 6 est 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.

Comment résoudre

Méthode simple

Tout d'abord, dans la méthode simple, nous devons trouver le plus grand diviseur impair de tous les éléments du tableau. Ensuite, en fonction de la plage de la requête, nous devons calculer le XOR de chaque élément de la plage et le renvoyer.

Approche efficace

Un moyen efficace de résoudre ce problème consiste à créer un tableau de préfixes XOR prefix_XOR[] contenant le tableau avec le plus grand diviseur impair, au lieu d'effectuer un XOR sur chaque nombre de la plage à chaque fois et de renvoyer prefix_XOR[R ] - prefix_XOR [L-1].

Le tableau Prefix XOR est un tableau où chaque élément contient le XOR de tous les éléments précédents.

Exemple

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

Sortie

7
4

Description du code ci-dessus

• Créez un tableau préfixe_XOR pour stocker le plus grand diviseur impair de chaque élément, puis remplacez ce tableau par un tableau préfixe XOR.

• Le plus grand diviseur impair est calculé en le divisant par deux jusqu'à ce que modulo 2 vous obteniez 1.

• Créez un tableau XOR de préfixe en parcourant le tableau et en effectuant un XOR au niveau du bit de l'élément actuel avec l'élément précédent.

• Le résultat de la requête est calculé en soustrayant l'index droit du tableau prefix_XOR[] (gauche - 1) L'index du tableau prefix_XOR[].

Conclusion

Dans ce didacticiel, nous avons discuté d'un problème dans lequel nous devons trouver le plus grand diviseur impair pour chaque nombre dans la plage d'un tableau donné à l'aide de XOR. Nous avons discuté d'un moyen de résoudre ce problème en trouvant le plus grand diviseur impair pour chaque élément et en utilisant un tableau de préfixes XOR. Nous avons également discuté d'un programme C++ pour ce problème et nous pouvons le faire en utilisant des langages de programmation comme C, Java, Python, etc. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!