关于区间最大奇数除数异或的质疑-yiteyi-C++库

给定一系列 N 正整数。有 Q 每个查询都包括一个范围[L，R]。对于每个查询，输出该范围内每个数字的最大奇数除数的异或。

null

例如：

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

其思想是预先计算数组的最大奇数除数，并将其存储在一个数组中，比如preXOR[]。现在，预计算并存储数组preXOR[]的前缀XOR。要回答每个查询，请返回（preXOR[r]xor preXOR[l-1]）。

以下是该方法的实施情况：

C++

                         #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

                         // 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                       

Python3

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

                         // 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                       

Javascript

                         <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>                       

输出：

本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章