Count the number of pair in Array with given XOR porperty A[i]^A[j] = i^j

By Ann Roberts On Mar 15, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given an array A[] with N elements, the task is to find the total number of pairs possible with A[i] ^ A[j] = i ^ j, considering base-indexing 1 and (i, j) are distinct.

Examples:

Input: arr[] = {4, 2, 3, 1}
Output: 2
Explanation: The array has 2 pairs: (4, 1) and (2, 3)

For (4, 1), 4^1 = 5 and their index 1^4 = 5

Similarly, for (2, 3), 2^3 = 1 and their index 2^3 = 1

Approach: This can be solved with the following idea:

Applying basic XOR principles, we can find that

Given: A[i]^A[j] = i^j

A[i] ^ A[j] ^ A[j] = i ^ j ^ A[j]

A[i] ^ i = i ^ i ^ j ^ A[j]

A[i] ^ i = A[j] ^ j

Thus, we basically need to find the total pair of elements possible with the same value of A[i]^i, where i is the index of the element in the array.

Steps involved in the implementation of code:

Calculate the XOR of arr[i] ^ (i). Store it in the map.
Increase the count of pairs by checking the frequency of each key and applying (n * (n-1)) /2.

Below is the Implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int getPairCount(int arr[], int n)

{

int count = 0;

map<int, int> mp;

for (int i = 0; i < n; i++)

mp[(arr[i] ^ (i + 1))]++;

for (auto itr : mp)

count += ((itr.second) * (itr.second - 1)) / 2;

return count;

}

int main()

{

int arr[] = { 4, 2, 3, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

cout << getPairCount(arr, n);

return 0;

}

Time Complexity: O(N), Since we have to run the loop only once.
Auxiliary Space: O(N), Temporary mapping of A[i]^i values.

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given an array A[] with N elements, the task is to find the total number of pairs possible with A[i] ^ A[j] = i ^ j, considering base-indexing 1 and (i, j) are distinct.

Examples:

Input: arr[] = {4, 2, 3, 1}
Output: 2
Explanation: The array has 2 pairs: (4, 1) and (2, 3)

For (4, 1), 4^1 = 5 and their index 1^4 = 5

Similarly, for (2, 3), 2^3 = 1 and their index 2^3 = 1

Approach: This can be solved with the following idea:

Applying basic XOR principles, we can find that

Given: A[i]^A[j] = i^j

A[i] ^ A[j] ^ A[j] = i ^ j ^ A[j]

A[i] ^ i = i ^ i ^ j ^ A[j]

A[i] ^ i = A[j] ^ j

Thus, we basically need to find the total pair of elements possible with the same value of A[i]^i, where i is the index of the element in the array.

Steps involved in the implementation of code:

Calculate the XOR of arr[i] ^ (i). Store it in the map.
Increase the count of pairs by checking the frequency of each key and applying (n * (n-1)) /2.

Below is the Implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int getPairCount(int arr[], int n)

{

int count = 0;

map<int, int> mp;

for (int i = 0; i < n; i++)

mp[(arr[i] ^ (i + 1))]++;

for (auto itr : mp)

count += ((itr.second) * (itr.second - 1)) / 2;

return count;

}

int main()

{

int arr[] = { 4, 2, 3, 1 };

int n = sizeof(arr) / sizeof(arr[0]);

cout << getPairCount(arr, n);

return 0;

}

Time Complexity: O(N), Since we have to run the loop only once.
Auxiliary Space: O(N), Temporary mapping of A[i]^i values.

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.