ในบทความนี้ เราจะอภิปรายการนับจำนวน unique triplets (x, y, z) ในอาร์เรย์ของตัวเลขที่ไม่ซ้ำกันที่กำหนด โดยที่ XOR ของพวกเขาเป็น 0 ดังนั้น triplets ควรจะเป็น unique โดยที่องค์ประกอบทั้งสามไม่ซ้ำกัน และนับทุก combination ของ triplets ตัวอย่างเช่น:
Input : arr[] = { 5, 6, 7, 1, 3 }
Output : 2
คำอธิบาย : triplets คือ { 5, 6, 3 } และ { 6, 7, 1 } ที่ XOR เท่ากับศูนย์
Input : arr[] = { 3, 6, 8, 1, 5, 4, 12 }
Output : 3
คำอธิบาย : Triplets คือ { 3, 6, 5 }, { 1, 5, 4 } และ { 4, 8, 12 } ที่ XOR เท่ากับศูนย์
วิธีการแก้ปัญหา
เรารู้ว่า XOR ของค่าเดียวกันจะให้ศูนย์เสมอ ดังนั้นเราหา unique triplets วิธีที่มีประสิทธิภาพสามารถนำมาใช้ได้ ซึ่งคือการหา XOR ของสองค่าจากอาร์เรย์และเก็บผลลัพธ์ไว้ และค้นหาค่าที่เท่ากับผลลัพธ์ในอาร์เรย์ นอกจากนี้ ค่าของผลลัพธ์ไม่ควรเท่ากับค่าใดๆ ในคู่ มองหา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 3, 6, 8, 1, 5, 4, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
int result;
// ตัวแปร count เพื่อนับคู่
int count = 0;
// สร้าง set เพื่อเก็บตัวเลขที่ไม่ซ้ำ
unordered_set values;
// แทรกค่าลงใน set
for (int i = 0; i < n; i++)
values.insert(arr[i]);
// วนลูปสำหรับทุกคู่เพื่อคำนวณ XOR
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) { // หา xor ของคู่ i, j
int XR = arr[i] ^ arr[j];
// ตรวจสอบว่าค่า XOR ของคู่มีอยู่ในอาร์เรย์
// และค่าไม่ควรอยู่ในคู่
if (values.find(XR) != values.end() && XR != arr[i] && XR != arr[j])
count++;
}
}
// เก็บผลลัพธ์
result = count / 3;
cout << "Number of unique triplets : " << result;
return 0;
} ผลลัพธ์
Number of unique triplets : 3
คำอธิบายโค้ด
- สร้าง set unordered_set
values; เพื่อเก็บตัวเลขที่ไม่ซ้ำของอาร์เรย์ที่กำหนด - ใช้ for() loop เพื่อแทรกค่าใน set โดยใช้ values.insert(arr[i])
- ใช้สอง nested loops เพื่อเดินทางผ่านทุกคู่และคำนวณค่า XOR ของพวกเขา
- จากนั้น ค้นหาค่า XOR ในอาร์เรย์ และเพิ่ม count ถ้าค่าถูกพบในอาร์เรย์และไม่อยู่ในคู่
- เก็บผลลัพธ์เป็น count / 3 เพราะจะนับ combination ของ triplets สามแบบ และเราต้องการ unique triplets
สรุป
บทความนี้อภิปรายการหาจำนวน triplets ที่มีค่า XOR เป็น 0 เราอภิปรายวิธีที่มีประสิทธิภาพในการหา unique triplets เรายังอภิปรายโปรแกรม C++ เพื่อแก้ปัญหา อย่างไรก็ตาม เราสามารถเขียนโปรแกรมนี้ในภาษาโปรแกรมมิ่งอื่นๆ เช่น Java, C, Python ฯลฯ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์
