Consultas sobre XOR del mayor divisor impar del rango

Dada una array de N enteros positivos. Hay consultas Q , cada una incluye un rango [L, R]. Para cada consulta, genera el xor del mayor divisor impar de cada número en ese rango.

Ejemplos: 

Input : arr[] = { 3, 4, 5 }
query 1: [0, 2]
query 2: [1, 2]
Output : 7 4
Greatest odd divisor are: { 3, 1, 5 }
XOR of 3, 1, 5 is 7
XOR of 1, 5 is 4

Input : arr[] = { 2, 1, 2 }
query 1: [0, 2]
Output : 1

La idea es precalcular el mayor divisor impar de la array y almacenarlo en una array, digamos preXOR[]. Ahora, calcule previamente y almacene el prefijo XOR de la array preXOR[]. Para responder a cada consulta, devuelva (preXOR[r] xor preXOR[l-1]).

A continuación se muestra la implementación de este enfoque: 

#include <bits/stdc++.h>
using namespace std;
 
// Precompute the prefix XOR of greatest
// odd divisor
void prefixXOR(int arr[], int preXOR[], int n)
{
    // Finding the Greatest Odd divisor
    for (int i = 0; i < n; i++) {
        while (arr[i] % 2 != 1)
            arr[i] /= 2;
 
        preXOR[i] = arr[i];
    }
 
    // Finding prefix XOR
    for (int i = 1; i < n; i++)
        preXOR[i] = preXOR[i - 1] ^ preXOR[i];
}
 
// Return XOR of the range
int query(int preXOR[], int l, int r)
{
    if (l == 0)
        return preXOR[r];
    else
        return preXOR[r] ^ preXOR[l - 1];
}
 
// Driven Program
int main()
{
    int arr[] = { 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int preXOR[n];
    prefixXOR(arr, preXOR, n);
 
    cout << query(preXOR, 0, 2) << endl;
    cout << query(preXOR, 1, 2) << endl;
 
    return 0;
}

// Java code Queries on XOR of
// greatest odd divisor of the range
import java.io.*;
 
class GFG
{
    // Precompute the prefix XOR of greatest
    // odd divisor
    static void prefixXOR(int arr[], int preXOR[], int n)
    {
        // Finding the Greatest Odd divisor
        for (int i = 0; i < n; i++)
        {
            while (arr[i] % 2 != 1)
                arr[i] /= 2;
     
            preXOR[i] = arr[i];
        }
     
        // Finding prefix XOR
        for (int i = 1; i < n; i++)
            preXOR[i] = preXOR[i - 1] ^ preXOR[i];
    }
     
    // Return XOR of the range
    static int query(int preXOR[], int l, int r)
    {
        if (l == 0)
            return preXOR[r];
        else
            return preXOR[r] ^ preXOR[l - 1];
    }
     
    // Driven Program
    public static void main (String[] args)
    {
        int arr[] = { 3, 4, 5 };
        int n = arr.length;
     
        int preXOR[] = new int[n];
        prefixXOR(arr, preXOR, n);
     
        System.out.println(query(preXOR, 0, 2)) ;
        System.out.println (query(preXOR, 1, 2));
     
             
    }
}
 
// This article is contributed by vt_m

# Precompute the prefix XOR of greatest
# odd divisor
def prefixXOR(arr, preXOR, n):
     
    # Finding the Greatest Odd divisor
    for i in range(0, n, 1):
        while (arr[i] % 2 != 1):
            arr[i] = int(arr[i] / 2)
 
        preXOR[i] = arr[i]
 
    # Finding prefix XOR
    for i in range(1, n, 1):
        preXOR[i] = preXOR[i - 1] ^ preXOR[i]
 
# Return XOR of the range
def query(preXOR, l, r):
    if (l == 0):
        return preXOR[r]
    else:
        return preXOR[r] ^ preXOR[l - 1]
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 4, 5]
    n = len(arr)
 
    preXOR = [0 for i in range(n)]
    prefixXOR(arr, preXOR, n)
 
    print(query(preXOR, 0, 2))
    print(query(preXOR, 1, 2))
     
# This code is contributed by
# Sahil_shelangia

// C# code Queries on XOR of
// greatest odd divisor of the range
using System;
 
class GFG
{
    // Precompute the prefix XOR of greatest
    // odd divisor
    static void prefixXOR(int []arr,
                    int []preXOR, int n)
    {
        // Finding the Greatest Odd divisor
        for (int i = 0; i < n; i++)
        {
            while (arr[i] % 2 != 1)
                arr[i] /= 2;
     
            preXOR[i] = arr[i];
        }
     
        // Finding prefix XOR
        for (int i = 1; i < n; i++)
            preXOR[i] = preXOR[i - 1] ^ preXOR[i];
    }
     
    // Return XOR of the range
    static int query(int [] preXOR, int l, int r)
    {
        if (l == 0)
            return preXOR[r];
        else
            return preXOR[r] ^ preXOR[l - 1];
    }
     
    // Driven Program
    public static void Main ()
    {
        int []arr = { 3, 4, 5 };
        int n = arr.Length;
     
        int []preXOR = new int[n];
        prefixXOR(arr, preXOR, n);
     
        Console.WriteLine(query(preXOR, 0, 2)) ;
        Console.WriteLine (query(preXOR, 1, 2));
    }
}
 
// This code is contributed by vt_m

<script>
 
// Javascript code queries on XOR of 
// greatest odd divisor of the range
 
// Precompute the prefix XOR of greatest
// odd divisor
function prefixXOR(arr, preXOR, n)
{
     
    // Finding the Greatest Odd divisor
    for(let i = 0; i < n; i++)
    {
        while (arr[i] % 2 != 1)
            arr[i] = parseInt(arr[i] / 2);
 
        preXOR[i] = arr[i];
    }
 
    // Finding prefix XOR
    for(let i = 1; i < n; i++)
        preXOR[i] = preXOR[i - 1] ^ preXOR[i];
}
 
// Return XOR of the range
function query(preXOR, l, r)
{
    if (l == 0)
        return preXOR[r];
    else
        return preXOR[r] ^ preXOR[l - 1];
}
 
// Driver code
let arr = [ 3, 4, 5 ];
let n = arr.length;
let preXOR = new Array(n);
 
prefixXOR(arr, preXOR, n);
 
document.write(query(preXOR, 0, 2) + "<br>");
document.write(query(preXOR, 1, 2) + "<br>");
 
// This code is contributed by subham348
 
</script>

7
4

Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.