กำหนดอาร์เรย์ arr[ ] ที่มีจำนวนเต็มบวกและค่าที่ตรงกัน เป้าหมายคือการหาชุดย่อยของ arr[] ที่มีองค์ประกอบที่มี XOR =ตรงกัน
ตัวอย่าง
อินพุต
arr[] = {4, 2, 8, 10} match=12 ผลลัพธ์
Count of number of subsets having a particular XOR value are: 2
คำอธิบาย
Subsets of arr with XOR of elements as 0 are − [ 4,8 ], [4,2,10]
อินพุต
arr[] = {3,5,2,7} match=5 ผลลัพธ์
Count of number of subsets having a particular XOR value are− 2
คำอธิบาย
ubsets of arr with XOR of elements as 0 are− [ 5 ], [2,7]
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะใช้โซลูชันการเขียนโปรแกรมแบบไดนามิก อาร์เรย์ arr_2[][] จะประกอบด้วยค่าที่ดัชนี i,j โดยที่ arr_2[ i ][ j ] มีค่า XOR ขององค์ประกอบจากชุดย่อยของ arr[ 0 ถึง i-1 ] ใช้ค่าเริ่มต้น arr_2[0][0] เป็น 1 สำหรับเซตว่าง XOR คือ 1.Set arr_2[i][j] =arr_2[i−1][j] + arr_2[i-1][j ^ arr[i−1]], หากเซตย่อย arr[0 ถึง i−2] มี XOR เป็น j ดังนั้นเซตย่อย arr[0 ถึง i−1] ก็มี XOR j นอกจากนี้ หากเซตย่อย arr[0 ถึง i−2] มี XOR เป็น j^arr[i] ดังนั้นเซตย่อย arr[0 ถึง i−1] ก็มี XOR j เป็น j ^ arr[i−1] ^ arr[i−1] .ผลลัพธ์จะอยู่ใน arr_2[ size ][ match ].
-
ใช้อาร์เรย์จำนวนเต็ม arr[].
-
ใช้การจับคู่ตัวแปรเป็นจำนวนเต็ม
-
ฟังก์ชัน subset_XOR(int arr[], int size, int match) รับอาร์เรย์อินพุตและความยาว และส่งคืนค่าจำนวนชุดย่อยที่มีค่า XOR เฉพาะ
-
เริ่มแรกรับสูงสุด =arr[0] ตอนนี้สำรวจทั้ง arr[] โดยใช้ for loop และหาค่าสูงสุดเป็นค่าสูงสุด
-
Compute temp =(1 <<(int)(log2(highest) + 1) ) − 1 เป็นค่า XOR สูงสุดที่เป็นไปได้
-
นำอาร์เรย์ arr_2[size+1][temp+1] มาเก็บ XOR
-
เริ่มต้น arr_2 ทั้งหมดด้วย 0s โดยใช้ for loop
-
ตั้งค่า arr_2[0][0] =1.
-
ใช้สำหรับการวนซ้ำจาก i=0 ถึง i<=size และ j=0 ถึง j<=size ตั้งค่า temp_2 =arr_2[i-1][j ^ arr[i−1]] และตั้งค่า arr_2[i][j ] =arr_2[i-1][j] + temp_2.
-
ในตอนท้ายของทั้งสองลูป เราจะมี arr_2[size][match] เป็นจำนวนเซ็ตย่อยที่มีค่า XOR เฉพาะ
-
ส่งคืน arr_2[size][match] เป็นผลลัพธ์
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int subset_XOR(int arr[], int size, int match){
int highest = arr[0];
for (int i = 1; i < size; i++){
if(arr[i] > highest){
highest = arr[i];
}
}
int temp = (1 << (int)(log2(highest) + 1) ) − 1;
if( match > temp){
return 0;
}
int arr_2[size+1][temp+1];
for (int i = 0; i<= size; i++){
for (int j = 0; j<= temp; j++){
arr_2[i][j] = 0;
}
}
arr_2[0][0] = 1;
for (int i=1; i<=size; i++){
for (int j=0; j<=temp; j++){
int temp_2 = arr_2[i−1][j ^ arr[i−1]];
arr_2[i][j] = arr_2[i−1][j] + temp_2;
}
}
return arr_2[size][match];
}
int main(){
int arr[] = {4, 2, 8, 10, 3, 4, 4};
int match = 2;
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of subsets having a particular XOR value are: "<<subset_XOR(arr, size, match);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of number of subsets having a particular XOR value are − 8
