ในบทความนี้ เราจะพูดถึงการนับจำนวนแฝดสามที่ไม่ซ้ำ (x, y, z) ในอาร์เรย์ของจำนวนเฉพาะที่กำหนดโดยที่ XOR ของพวกมันเป็น 0 ดังนั้น แฝดสามควรไม่ซ้ำกันโดยที่องค์ประกอบทั้งสามนั้นไม่ซ้ำกัน และจะนับทั้งหมด การรวมกันของแฝดสาม เช่น −
Input : arr[ ] = { 5, 6, 7, 1, 3 }
Output : 2
Explanation : triplets are { 5, 6, 3 } and { 6, 7, 1 } whose XOR is zero.
Input : arr[ ] = { 3, 6, 8, 1, 5, 4 , 12}
Output : 3
Explanation : Triplets are { 3, 6, 5 }, { 1, 5, 4 } and { 4, 8, 12 } whose XOR is zero. แนวทางในการหาทางออก
เรารู้ว่า XOR มีค่าเท่ากันจะให้ศูนย์เสมอ ดังนั้นเราจึงพบแฝดสามที่ไม่ซ้ำกัน ซึ่งสามารถใช้แนวทางในแง่ดีได้ ซึ่งก็คือการค้นหา 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 variable to keep count of pairs.
int count = 0;
// creating a set to store unique numbers .
unordered_set < int >values;
// inserting values in set.
for (int i = 0; i < n; i++)
values.insert (arr[i]);
// traverse for all pairs to calculate XOR.
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) { // finding xor of i, j pair.
int XR = arr[i] ^ arr[j];
// checking if XOR value of pair present in array
// and value should not be in pairs.
if (values.find (XR) != values.end () && XR != arr[i] &&
XR != arr[j])
count++;
}
}
// storing result
result = count / 3;
cout << "Number of unique triplets : " << result;
return 0;
} ผลลัพธ์
Number of unique triplets : 3
คำอธิบายของโค้ดด้านบน
- การสร้างชุด unordered_set
values; เพื่อจัดเก็บหมายเลขเฉพาะของอาร์เรย์ที่กำหนด - การใช้ for() วนซ้ำเพื่อแทรกค่าในชุดโดยใช้ values.insert (arr[i])
- ใช้สองลูปที่ซ้อนกันเพื่อสำรวจคู่ทั้งหมดและคำนวณค่า XOR ของพวกมัน
- จากนั้น ค้นหาค่า XOR ในอาร์เรย์และเพิ่มจำนวนหากพบค่าในอาร์เรย์และไม่ใช่เป็นคู่
- การจัดเก็บผลลัพธ์เป็นจำนวน / 3 จะนับชุดค่าผสมสามชุดของแฝดสาม และเราต้องการชุดค่าผสมสามชุดที่ไม่ซ้ำกัน
บทสรุป
บทความนี้กล่าวถึงการหาจำนวนแฝดที่มีค่า XOR 0; เราได้พูดคุยถึงแนวทางการมองโลกในแง่ดีเพื่อค้นหาแฝดสามตัวที่ไม่เหมือนใคร เรายังพูดถึงโปรแกรม C++ เพื่อแก้ปัญหา อย่างไรก็ตาม เราสามารถเขียนโปรแกรมนี้ในภาษาการเขียนโปรแกรมอื่นๆ เช่น Java, C, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
