XOR query for maximum odd divisor in range in C++

Given an array of N integers and Q range queries. For each query, we need to return the XOR of the largest odd divisor of each number in the range.

The largest odd divisor is the largest odd number that can divide the number N, such as . For example, the largest odd divisor of 6 is 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.

Solution method

Simple method

First, in the simple method, we need to find the largest odd divisor of all array elements. Then based on the range of the query, we need to calculate the XOR of each element in the range and return it.

Efficient method

An effective way to solve this problem is to create a prefix XOR array prefix_XOR[] containing the array with the largest odd divisor, instead of each number in the range each time Performs an XOR and returns prefix_XOR[R] - prefix_XOR[L-1].

Prefix XOR array is an array in which each element contains the XOR of all previous elements.

Example

#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

Description of the above code

• Create a prefix_XOR array to store the largest odd divisor of each element, Then change this array to a prefix XOR array.

• The largest odd divisor is calculated by dividing it by two until modulo 2 gives 1.

• Create a prefix XOR array by traversing the array and performing a bitwise XOR of the current element with the previous element.

• The query result is calculated by subtracting the right index of the prefix_XOR[] array (left - 1) The index of the prefix_XOR[] array.

Conclusion

In this tutorial, we discussed a problem where we need to find the largest odd divisor for each number in the range of a given array. We discussed a way to solve this problem by finding the largest odd divisor for each element and using a prefix XOR array. We also discussed C program for this problem and we can do this using programming languages ​​like C, Java, Python etc. We hope this article was helpful to you.

The above is the detailed content of XOR query for maximum odd divisor in range in C++. For more information, please follow other related articles on the PHP Chinese website!