Tìm giá trị XOR lớn nhất của con mảng kích thước k trong C++

Mô tả vấn đề

Cho mảng arr[] n phần tử và số nguyên k. Tìm giá trị XOR lớn nhất của các con mảng liên tiếp kích thước k.

Ví dụ minh họa

Đầu vào:

arr[] = {3, 1, 6, 2, 7, 9}, k = 3

Đầu ra:

12

Giải thích:

Các con mảng và XOR:
{3,1,6} = 4
{1,6,2} = 5
{6,2,7} = 3
{2,7,9} = 12  ← Max

Phương pháp giải quyết

Cách đơn giản (O(n*k)): Hai vòng lặp lồng nhau, tính XOR từng con mảng.

Cách tối ưu (O(n) - Sliding Window XOR): Tính XOR cửa sổ đầu tiên. Khi trượt cửa sổ, dùng tính chất x ^ a ^ x = a để "xóa" phần tử cũ và thêm phần tử mới: currentXOR = currentXOR ^ arr[i-k] ^ arr[i]. Cập nhật maxXor.

Chương trình minh họa

#include <iostream>
using namespace std;

int findMaxSubArrayXOR(int arr[], int n, int k) {
    int currentXORVal = 0;
    for (int i = 0; i < k; i++)
        currentXORVal ^= arr[i];
    int maxXor = currentXORVal;
    for (int i = k; i < n; i++) {
        currentXORVal ^= arr[i - k];
        currentXORVal ^= arr[i];
        maxXor = max(maxXor, currentXORVal);
    }
    return maxXor;
}

int main() {
    int arr[] = {3, 1, 6, 2, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Giá trị XOR lớn nhất của con mảng kích thước " << k << " là " << findMaxSubArrayXOR(arr, n, k);
    return 0;
}

Kết quả đầu ra

Giá trị XOR lớn nhất của con mảng kích thước 3 là 12