Эффективное решение этой проблемы может иметь O(n) сложность времени.Идея основана на том факте, что arr[i] ^ arr[j] равно 2 тогда и только тогда, когда arr[i] ^ 2 равно arr[j].
1) Initialize result as 0.
2) Create an empty hash set "s".
3) Do following for each element arr[i] in arr[]
(a) If 2 ^ arr[i] is in "s", then increment result by 1.
(b) Insert arr[i] into the hash set "s".
3) return result.
Вот реализация C ++:
int xorPairCount(vector<int>& arr) {
int n= (int)arr.size();
int result = 0;
unordered_set<int> s;
for (int i = 0; i < n ; i++) {
// If there exist an element in set s
// with XOR equals to 2^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// 2, then increment count.
if (s.find(2^arr[i]) != s.end())
result++;
// Make element visited
s.insert(arr[i]);
}
return result;
}
Обратите внимание, что для этого решения я предположил, что в массиве нет дубликатов.Если дубликат разрешен, то решение будет немного другим.Дайте мне знать.
Обновление
Если в массиве есть дубликаты, используйте хэш-карту вместо хэш-набора для подсчета частоты каждого числа, потому что для каждого вхождения будет один счет.Вот обновление вышеуказанного кода:
int xorPairCount(vector<int>& arr) {
int n= (int)arr.size();
int result = 0;
unordered_map<int, int> m;
for (int i = 0; i < n ; i++) {
int curr_xor = 2^arr[i];
if (m.find(curr_xor) != m.end())
result += m[curr_xor];
m[arr[i]]++;
}
return result;
}