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

Given an array A[] with N components, the duty is to search out the whole 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
Clarification: 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 ideas, we will 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 principally want to search out the whole pair of components 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.
• Improve 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:

Time Complexity: O(N), Since we now have to run the loop solely as soon as.
Auxiliary Area: O(N), Momentary mapping of A[i]^i values.