資料結構
網路
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 次檢視
廣告