Wednesday, March 15, 2023
HomeSoftware DevelopmentDepend the variety of pair in Array with given XOR porperty A^A...

# Depend the variety of pair in Array with given XOR porperty A[i]^A[j] = i^j

Given an array A[] with N parts, the duty is to seek out the overall variety of pairs doable with A[i] ^ A[j] = i ^ j, contemplating base-indexing 1 and (i, j) are distinct.

Examples:

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

• For (4, 1), 4^1 = 5 and their index 1^4 = 5
• Equally, for (2, 3), 2^3 = 1 and their index 2^3 = 1

Method: This may be solved with the next concept:

Making use of primary XOR rules, we are able to discover 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 mainly want to seek out the overall pair of parts doable with the identical worth of A[i]^i, the place i is the index of the ingredient within the array.

Steps concerned within the implementation of code:

• Calculate the XOR of arr[i] ^ (i). Retailer it within the map.
• Enhance the rely of pairs by checking the frequency of every key and making use of (n * (n-1)) /2.

Beneath is the Implementation of the above method:

## C++

 `#embrace ` `utilizing` `namespace` `std;` `Â `Â  `int` `getPairCount(``int` `arr[], ``int` `n)` `{` `Â Â Â Â ``int` `rely = 0;` `Â Â Â Â ``map<``int``, ``int``> mp;` `Â `Â  `Â Â Â Â ` `Â Â Â Â ``for` `(``int` `i = 0; i < n; i++)` `Â Â Â Â Â Â Â Â ``mp[(arr[i] ^ (i + 1))]++;` `Â `Â  `Â Â Â Â ` `Â Â Â Â ``for` `(``auto` `itr : mp)` `Â Â Â Â Â Â Â Â ` `Â Â Â Â Â Â Â Â ``rely += ((itr.second) * (itr.second - 1)) / 2;` `Â Â Â Â ``return` `rely;` `}` `Â `Â  `int` `major()` `{` `Â Â Â Â ``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’ve got to run the loop solely as soon as.
Auxiliary Area: O(N), Short-term mapping of A[i]^i values.

RELATED ARTICLES