home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หาค่า XOR สูงสุดของซับอาร์เรย์ขนาด k ใน C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็ม k ต้องการหา ค่า XOR สูงสุด (Maximum XOR) ของซับอาร์เรย์ทุกชุดที่มีขนาด k

ตัวอย่าง

Input: arr[] = {3, 1, 6, 2, 7, 9}, k = 3
Output: 12

คำอธิบาย: XOR ของซับอาร์เรย์ขนาด 3 ทุกชุด:

  • {3, 1, 6} = 3^1^6 = 4
  • {1, 6, 2} = 1^6^2 = 5
  • {6, 2, 7} = 6^2^7 = 3
  • {2, 7, 9} = 2^7^9 = 12 (สูงสุด)

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force (Two Loops)

ลูปนอกเดินทุกตำแหน่งเริ่มต้น ลูปในคำนวณ XOR ของ k ตัว → Time: O(n×k)

วิธีที่ 2: Sliding Window XOR (มีประสิทธิภาพ O(n))

ใช้คุณสมบัติของ XOR: x ^ a ^ x = a (การ XOR ซ้ำสองครั้งจะยกเลิกกัน)

  1. คำนวณ XOR ของ Window แรก (index 0 ถึง k-1) → currentXORVal
  2. ตั้ง maxXor = currentXORVal
  3. Slide Window:
    • currentXORVal ^= arr[i-k] → "ลบ" สมาชิกเก่าออก (XOR อีกครั้ง)
    • currentXORVal ^= arr[i] → "บวก" สมาชิกใหม่เข้า
    • อัปเดต maxXor = max(maxXor, currentXORVal)

โค้ดตัวอย่าง C++

#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 << "The maximum XOR of subarray of size " << k << " is " << findMaxSubArrayXOR(arr, n, k);
    return 0;
}

ผลลัพธ์

The maximum XOR of subarray of size 3 is 12