# Count pairs from an array having sum of twice of their AND and XOR equal to K

Given an array **arr[]** consisting of** N **integers and an integer **K**, the task is to count the number of pairs satisfying the equation **2*(arr[i] & arr[j]) + (arr[i] ^ arr[j]) = K.**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {1, 5, 4, 8, 7}, K = 9Output:2Explanation:

- Elements at index 0 and 3, i.e. arr[i] = 1, arr[j] = 8, satisfies the given equations.
- Elements at index 1 and 2, i.e. arr[i] = 5, arr[j] = 4, satisfies the given equations.

Input:arr[] = {1, 2, 2, 4, 5}, K = 3Output:2

**Naive Approach: **The simplest approach is to generate all possible pairs from the array and for each pair, check if the pair satisfies the given equation or not. **Time Complexity: **O(N^{2})**Auxiliary Space:** O(1)

**Efficient Approach: **The above approach can be optimized based on the following observations:

Observation:

A + B = (A ^ B) + 2 * (A & B)

While calculating sum, if both bits are1(i.e., AND is 1), the resultant bit is0, and1is added as carry, which means every bit inANDisleft-shiftedby1, i.e. value ofANDis multiplied by2and added.Therefore, A + B = given equations.

Hence, this verifies the above observation.

Follow the below steps to solve the problem:

- The problem now reduces to Two Sum problem and the task reduces to count pairs whose sum is equal to
**K.** - Initialize an unordered_map, say
**mp**, and a variable, say**cnt**, to count the number of pairs satisfying the given conditions. - Traverse the array and for each element:
- If
**mp[K – arr[i]]**is not zero, then add its value to**cnt**. - Update the frequency of
**arr[i]**in**Map**.

- If
- Print the
**cnt**as the answer.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count number of pairs` `// satisfying the given conditions` `void` `countPairs(` `int` `arr[], ` `int` `N, ` `int` `K)` `{` ` ` `// Stores the frequency of array elements` ` ` `unordered_map<` `int` `, ` `int` `> mp;` ` ` `// Stores the total number of pairs` ` ` `int` `cnt = 0;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Add it to cnt` ` ` `cnt += mp[K - arr[i]];` ` ` `// Update frequency of` ` ` `// current array element` ` ` `mp[arr[i]]++;` ` ` `}` ` ` `// Print the count` ` ` `cout << cnt;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given array` ` ` `int` `arr[] = { 1, 5, 4, 8, 7 };` ` ` `// Size of the array` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `// Given value of K` ` ` `int` `K = 9;` ` ` `countPairs(arr, N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `import` `java.util.*;` `class` `GFG` `{` ` ` `// Function to count number of pairs` ` ` `// satisfying the given conditions` ` ` `static` `void` `countPairs(` `int` `arr[], ` `int` `N, ` `int` `K)` ` ` `{` ` ` ` ` `// Stores the frequency of array elements` ` ` `Map<Integer, Integer> mp = ` `new` `HashMap<>();` ` ` `// Stores the total number of pairs` ` ` `int` `cnt = ` `0` `;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++)` ` ` `{` ` ` `// Add it to cnt` ` ` `if` `(mp.get(K - arr[i]) != ` `null` `)` ` ` `cnt += mp.get(K - arr[i]);` ` ` `// Update frequency of` ` ` `// current array element` ` ` `mp.put(arr[i], mp.get(arr[i]) == ` `null` ` ` `? ` `1` ` ` `: mp.get(arr[i]) + ` `1` `);` ` ` `}` ` ` `// Print the count` ` ` `System.out.println(cnt);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// Given array` ` ` `int` `arr[] = { ` `1` `, ` `5` `, ` `4` `, ` `8` `, ` `7` `};` ` ` `// Size of the array` ` ` `int` `N = arr.length;` ` ` `// Given value of K` ` ` `int` `K = ` `9` `;` ` ` `countPairs(arr, N, K);` ` ` `}` `}` `// This code is contributed by Dharanendra L V` |

## Python3

`# Python3 program for the above approach` `from` `collections ` `import` `defaultdict` `# Function to count number of pairs` `# satisfying the given conditions` `def` `countPairs(arr, N, K) :` ` ` ` ` `# Stores the frequency of array elements` ` ` `mp ` `=` `defaultdict(` `int` `)` ` ` `# Stores the total number of pairs` ` ` `cnt ` `=` `0` ` ` `# Traverse the array` ` ` `for` `i ` `in` `range` `(N):` ` ` `# Add it to cnt` ` ` `cnt ` `+` `=` `mp[K ` `-` `arr[i]]` ` ` `# Update frequency of` ` ` `# current array element` ` ` `mp[arr[i]] ` `+` `=` `1` ` ` ` ` `# Print the count` ` ` `print` `(cnt)` `# Driver Code` `# Given array` `arr ` `=` `[ ` `1` `, ` `5` `, ` `4` `, ` `8` `, ` `7` `]` `# Size of the array` `N ` `=` `len` `(arr)` `# Given value of K` `K ` `=` `9` `countPairs(arr, N, K)` `# This code is contributed by sanjoy_62.` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `public` `class` `GFG` `{` ` ` `// Function to count number of pairs` ` ` `// satisfying the given conditions` ` ` `static` `void` `countPairs(` `int` `[] arr, ` `int` `N, ` `int` `K)` ` ` `{` ` ` ` ` `// Stores the frequency of array elements` ` ` `Dictionary<` `int` `, ` `int` `> mp` ` ` `= ` `new` `Dictionary<` `int` `, ` `int` `>();` ` ` `// Stores the total number of pairs` ` ` `int` `cnt = 0;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Add it to cnt` ` ` `if` `(mp.ContainsKey(K - arr[i]))` ` ` `cnt += mp[K - arr[i]];` ` ` `// Update frequency of` ` ` `// current array element` ` ` `if` `(mp.ContainsKey(arr[i])) {` ` ` ` ` `var` `val = mp[arr[i]];` ` ` `mp.Remove(arr[i]);` ` ` `mp.Add(arr[i], val + 1);` ` ` `}` ` ` `else` `{` ` ` ` ` `mp.Add(arr[i], 1);` ` ` `}` ` ` `}` ` ` `// Print the count` ` ` `Console.WriteLine(cnt);` ` ` `}` ` ` `// Driver Code` ` ` `static` `public` `void` `Main()` ` ` `{` ` ` `// Given array` ` ` `int` `[] arr = { 1, 5, 4, 8, 7 };` ` ` `// Size of the array` ` ` `int` `N = arr.Length;` ` ` `// Given value of K` ` ` `int` `K = 9;` ` ` `countPairs(arr, N, K);` ` ` `}` `}` `// This code is contributed by Dharanendra L V` |

## Javascript

`<script>` ` ` `// JavaScript program for the above approach` ` ` `// Function to count number of pairs` ` ` `// satisfying the given conditions` ` ` `function` `countPairs(arr,N,K)` ` ` `{` ` ` `// Stores the frequency of array elements` ` ` `let mp = ` `new` `Map();` ` ` `// Stores the total number of pairs` ` ` `let cnt = 0;` ` ` `// Traverse the array` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// Add it to cnt` ` ` `if` `(mp.has(K - arr[i]))` ` ` `{` ` ` `cnt += mp.get(K - arr[i]);` ` ` `}` ` ` `// Update frequency of` ` ` `// current array element` ` ` `if` `(mp.has(arr[i]))` ` ` `{` ` ` `mp.set(arr[i], mp.get(arr[i]) + 1);` ` ` `}` ` ` `else` `{` ` ` `mp.set(arr[i], 1);` ` ` `}` ` ` `}` ` ` `// Print the count` ` ` `document.write(cnt);` ` ` `}` ` ` `// Driver Code` ` ` `// Given array` ` ` `let arr = [ 1, 5, 4, 8, 7 ];` ` ` `// Size of the array` ` ` `let N = arr.length;` ` ` `// Given value of K` ` ` `let K = 9;` ` ` `countPairs(arr, N, K);` `</script>` |

**Output:**

2

**Time Complexity: **O(N)**Auxiliary Space: **O(N)