数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 范围内异或最大奇数约数查询
给定一个包含 N 个整数的数组和 Q 个范围查询。对于每个查询，我们需要返回该范围内每个数字的最大奇数约数的异或结果。
最大奇数约数是指能整除数字 N 的最大奇数，例如：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.解决方法
简单方法
首先，在简单方法中，我们需要找到所有数组元素的最大奇数约数。然后根据查询的范围，我们需要计算范围内每个元素的异或结果并返回。
高效方法
解决此问题的一种有效方法是创建一个包含最大奇数约数的数组前缀异或数组 prefix_XOR[]，而不是每次都查找范围内每个数字的异或结果并返回 prefix_XOR[R] - prefix_XOR[L-1]。
前缀异或数组是一个数组，其中每个元素都包含所有先前元素的异或结果。
示例
#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;
}输出
7 4
以上代码的解释
创建 prefix_XOR 数组以存储每个元素的最大奇数约数，然后将此数组更改为前缀异或数组。
最大奇数约数是通过将其除以 2 直到其模 2 等于 1 来计算的。
前缀异或数组是通过遍历数组并将当前元素与前一个元素进行按位异或来创建的。
查询结果是通过从 prefix_XOR[] 数组的右索引中减去 prefix_XOR[] 数组的（左 - 1）索引来计算的。
结论
在本教程中，我们讨论了一个问题，我们需要找到给定数组范围内每个数字的最大奇数约数的异或结果。我们讨论了一种通过查找每个元素的最大奇数约数并使用前缀异或数组来解决此问题的方法。我们还讨论了此问题的 C++ 程序，我们可以使用 C、Java、Python 等编程语言来实现。希望本文对您有所帮助。
更新于：2021年11月26日
121 次查看
广告