이 기사에서 우리는 XOR이 0인 주어진 고유 숫자 배열에서 고유한 삼중항(x, y, z)의 수를 계산하는 것에 대해 논의할 것입니다. 따라서 삼중항은 세 요소가 모두 고유하고 모두를 계산할 때 고유해야 합니다. 예를 들어 삼중항의 조합 -
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은 항상 0을 제공한다는 것을 알고 있습니다. 그래서 우리는 고유한 삼중항을 찾고, 배열에서 두 값의 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
값 세트 생성; 주어진 배열의 고유 번호를 저장합니다. - for() 루프를 사용하여 values.insert(arr[i])를 사용하여 집합에 값을 삽입합니다.
- 2개의 중첩 루프를 사용하여 모든 쌍을 순회하고 XOR 값을 계산합니다.
- 그런 다음 배열에서 XOR 값을 검색하고 값이 쌍이 아닌 배열에서 발견되면 개수를 증가시킵니다.
- 결과를 count / 3으로 저장하면 트리플렛의 세 가지 조합이 계산되며 고유한 트리플렛이 필요합니다.
결론
이 기사에서는 XOR 값이 0인 삼중항의 수를 찾는 방법에 대해 설명했습니다. 우리는 독특한 세쌍둥이를 찾기 위한 낙관적인 접근 방식에 대해 논의했습니다. 우리는 또한 문제를 해결하기 위한 C++ 프로그램에 대해 논의했습니다. 그러나 이 프로그램은 Java, C, Python 등과 같은 다른 프로그래밍 언어로 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.