Cho một mảng gồm N số nguyên và Q truy vấn trong phạm vi. Đối với mỗi truy vấn, chúng ta cần trả về XOR của ước số lẻ lớn nhất của mỗi số trong phạm vi.
Ước số lẻ lớn nhất là số lẻ lớn nhất có thể chia số N, ví dụ:Ví dụ:ước số lẻ lớn nhất của 6 là 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. Phương pháp tiếp cận để tìm giải pháp
Cách tiếp cận đơn giản
Đầu tiên, theo cách tiếp cận đơn giản, chúng ta cần tìm các ước số lẻ lớn nhất của tất cả các phần tử mảng. Sau đó, theo phạm vi của truy vấn, chúng tôi cần tính XOR của từng phần tử trong phạm vi và trả về.
Phương pháp tiếp cận hiệu quả
Một cách hiệu quả để giải quyết vấn đề này là tạo tiền tố mảng XOR prefix_XOR [] của mảng chứa các số chia lẻ lớn nhất thay vì mỗi lần tìm XOR của mỗi số trong phạm vi và trả về prefix_XOR [R] - prefix_XOR [L-1 ].
Mảng xor tiền tố là mảng trong đó mỗi phần tử chứa xor của tất cả các phần tử trước đó.
Ví dụ
#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;
} Đầu ra
7 4
Giải thích về Quy tắc trên
-
Mảng prefix_XOR được tạo để lưu trữ ước số lẻ lớn nhất của mỗi phần tử và sau đó thay đổi mảng này thành mảng XOR tiền tố.
-
Ước số lẻ lớn nhất được tính bằng cách chia nó cho hai cho đến khi modulo 2 cho 1.
-
Mảng xor tiền tố được tạo bằng cách duyệt qua mảng và thực hiện XOR theo từng bit của phần tử hiện tại với phần tử trước đó.
-
Kết quả của một truy vấn được tính bằng cách trừ chỉ số bên phải của mảng prefix_XOR [] với (bên trái - 1) chỉ số của mảng prefix_XOR [].
Kết luận
Trong hướng dẫn này, chúng ta đã thảo luận về một vấn đề trong đó chúng ta cần tìm XOR của ước số lẻ lớn nhất của mỗi số trong phạm vi của mảng đã cho. Chúng tôi đã thảo luận về một cách tiếp cận để giải quyết vấn đề này bằng cách tìm ước số lẻ lớn nhất của mỗi phần tử và sử dụng mảng xor tiền tố. Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.