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++
// C++ program to Count total possible// pairs with A[i]^A[j] = i^j in an array#include <bits/stdc++.h>using namespace std;// Function to count pairsint getPairCount(int arr[], int n){ int count = 0; map<int, int> mp; // Storing frequency of each key for (int i = 0; i < n; i++) mp[(arr[i] ^ (i + 1))]++; // Calculating the count of pairs for (auto itr : mp) // nC2 = (n*(n-1))/2 count += ((itr.second) * (itr.second - 1)) / 2; return count;}// Driver Codeint main(){ int arr[] = { 4, 2, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << getPairCount(arr, n); return 0;} |
Java
// Java program to Count total possible// pairs with A[i]^A[j] = i^j in an arrayimport java.util.*;public class GFG { // Function to count pairs public static int getPairCount(int[] arr, int n) { int count = 0; Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Storing frequency of each key for (int i = 0; i < n; i++) mp.put(arr[i] ^ (i + 1), mp.getOrDefault(arr[i] ^ (i + 1), 0) + 1); // Calculating the count of pairs for (Map.Entry<Integer, Integer> entry : mp.entrySet()) // nC2 = (n*(n-1))/2 count += ((entry.getValue()) * (entry.getValue() - 1)) / 2; return count; } // Driver code public static void main(String[] args) { int[] arr = {4, 2, 3, 1}; int n = arr.length; // Function call System.out.println(getPairCount(arr, n)); }} |
Python3
# Python program to count total possible# pairs with A[i]^A[j] = i^j in an arrayfrom collections import defaultdict# Function to count pairsdef getPairCount(arr, n): count = 0 mp = defaultdict(int) # Storing frequency of each key for i in range(n): mp[(arr[i] ^ (i + 1))] += 1 # Calculating the count of pairs for itr in mp: # nC2 = (n*(n-1))/2 count += ((mp[itr]) * (mp[itr] - 1)) // 2 return count# Drive Codearr = [4, 2, 3, 1]n = len(arr)# Function callprint(getPairCount(arr, n))# This Code is contributed by nikhilsainiofficial546 |
C#
using System;using System.Collections.Generic;class Program{ // Function to count pairs static int getPairCount(int[] arr, int n) { int count = 0; Dictionary<int, int> mp = new Dictionary<int, int>(); // Storing frequency of each key for (int i = 0; i < n; i++) { int key = arr[i] ^ (i + 1); if (mp.ContainsKey(key)) { mp[key]++; } else { mp[key] = 1; } } // Calculating the count of pairs foreach (KeyValuePair<int, int> kvp in mp) { // nC2 = (n*(n-1))/2 count += (kvp.Value * (kvp.Value - 1)) / 2; } return count; } // Driver Code static void Main(string[] args) { int[] arr = { 4, 2, 3, 1 }; int n = arr.Length; // Function call Console.WriteLine(getPairCount(arr, n)); }} |
Javascript
// JS program to Count total possible// pairs with A[i]^A[j] = i^j in an array// Function to count pairsfunction getPairCount(arr) { let count = 0; const mp = new Map(); // Storing frequency of each key for (let i = 0; i < arr.length; i++) { mp.set((arr[i] ^ (i + 1)), (mp.get((arr[i] ^ (i + 1))) || 0) + 1); } // Calculating the count of pairs for (let [key, value] of mp) { // nC2 = (n*(n-1))/2 count += ((value) * (value - 1)) / 2; } return count;}// Driver Codeconst arr = [4, 2, 3, 1];const n = arr.length;// Function callconsole.log(getPairCount(arr, n)); |
Output
2
Time Complexity: O(N), Since we have to run the loop only once.
Auxiliary Space: O(N), Temporary mapping of A[i]^i values.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
