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:
Input: arr[] = {1, 5, 4, 8, 7}, K = 9
Output: 2
Explanation:
- 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 = 3
Output: 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(N2)
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 are 1(i.e., AND is 1), the resultant bit is 0, and 1 is added as carry, which means every bit in AND is left-shifted by 1, i.e. value of AND is multiplied by 2 and 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.
- 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 conditionsvoid 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 Codeint 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 approachimport 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 approachfrom collections import defaultdict# Function to count number of pairs# satisfying the given conditionsdef 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 arrayarr = [ 1, 5, 4, 8, 7 ]# Size of the arrayN = len(arr) # Given value of KK = 9countPairs(arr, N, K)# This code is contributed by sanjoy_62. |
C#
// C# program for the above approachusing 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)
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!
