Trong bài viết này, chúng ta sẽ thảo luận về việc đếm số lượng các bộ ba duy nhất (x, y, z) trong một mảng các số duy nhất đã cho mà XOR của chúng là 0. Vì vậy, các bộ ba phải là duy nhất khi cả ba phần tử là duy nhất và sẽ đếm tất cả ví dụ như sự kết hợp của các bộ ba -
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. Phương pháp tiếp cận để tìm ra giải pháp
Chúng ta biết XOR của các giá trị giống nhau luôn cho kết quả bằng không. Vì vậy, chúng tôi tìm thấy các bộ ba duy nhất, một cách tiếp cận lạc quan có thể được áp dụng, đó là tìm XOR của hai giá trị từ một mảng và lưu trữ kết quả và tìm kiếm giá trị bằng với kết quả trong mảng. Ngoài ra, giá trị của kết quả không được bằng bất kỳ giá trị nào trong từng cặp. Tìm kiếm
Ví dụ
#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;
} Đầu ra
Number of unique triplets : 3
Giải thích về đoạn mã trên
- Tạo một tập hợp các giá trị
không có thứ tự; để lưu trữ các số duy nhất của một mảng nhất định. - Sử dụng vòng lặp for () để chèn các giá trị trong bộ bằng giá trị value.insert (arr [i]).
- Sử dụng hai vòng lặp lồng nhau để xem qua tất cả các cặp và tính giá trị XOR của chúng.
- Sau đó, tìm kiếm giá trị XOR trong mảng và tăng số lượng nếu giá trị được tìm thấy trong một mảng chứ không phải theo cặp.
- Lưu trữ kết quả dưới dạng số đếm / 3 sẽ đếm các kết hợp ba bộ ba và chúng tôi yêu cầu các bộ ba duy nhất.
Kết luận
Bài viết này thảo luận về việc tìm số bộ ba có giá trị XOR 0; chúng tôi đã thảo luận về một cách tiếp cận lạc quan để tìm ra những cặp sinh ba độc nhất. Chúng tôi cũng đã thảo luận về chương trình C ++ để giải quyết vấn đề. Tuy nhiên, chúng tôi có thể viết chương trình này bằng bất kỳ ngôn ngữ lập trình nào khác như Java, C, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.