Count pairs in an array such that both elements has equal set bits
Given an array arr [] of size N with unique elements, the task is to count the total number of pairs of elements that have equal set bits count.
Examples:
Input: arr[] = {2, 5, 8, 1, 3}
Output: 4
Set bits counts for {2, 5, 8, 1, 3} are {1, 2, 1, 1, 2}
All pairs with same set bits count are {2, 8}, {2, 1}, {5, 3}, {8, 1}Input: arr[] = {1, 11, 7, 3}
Output: 1
Only possible pair is {11, 7}
Approach:
- Traverse the array from left to right and count total number of set bits of each integer.
- Use a map to store the number of elements with same count of set bits with set bits as key, and count as value.
- Then iterator through map elements, and calculate how many two-element pairs can be formed from n elements (for each element of the map) i.e. (n * (n-1)) / 2.
- The final result will be the sum of output from the previous step for every element of the map.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to count all pairs // with equal set bits count int totalPairs( int arr[], int n) { // map to store count of elements // with equal number of set bits map< int , int > m; for ( int i = 0; i < n; i++) { // inbuilt function that returns the // count of set bits of the number m[__builtin_popcount(arr[i])]++; } map< int , int >::iterator it; int result = 0; for (it = m.begin(); it != m.end(); it++) { // there can be (n*(n-1)/2) unique two- // element pairs to choose from n elements result += (*it).second * ((*it).second - 1) / 2; } return result; } // Driver code int main() { int arr[] = { 7, 5, 3, 9, 1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << totalPairs(arr, n); return 0; } |
Java
import java.util.*; class GFG { /* Function to get no of set bits in binary representation of passed binary no. */ static int countSetBits( int n) { int count = 0 ; while (n > 0 ) { n &= (n - 1 ) ; count++; } return count; } // Function to count all pairs // with equal set bits count static int totalPairs( int arr[], int n) { // map to store count of elements // with equal number of set bits HashMap<Integer, Integer> m = new HashMap<>(); for ( int i = 0 ; i < n; i++) { // function that returns the // count of set bits of the number int count = countSetBits(arr[i]); if (m.containsKey(count)) m.put(count, m.get(count) + 1 ); else m.put(count, 1 ); } int result = 0 ; for (Map.Entry<Integer, Integer> entry : m.entrySet()) { int value = entry.getValue(); // there can be (n*(n-1)/2) unique two- // element pairs to choose from n elements result += ((value * (value - 1 )) / 2 ); } return result; } public static void main (String[] args) { int arr[] = { 7 , 5 , 3 , 9 , 1 , 2 }; int n = arr.length; System.out.println(totalPairs(arr, n)); } } |
Python3
# Python3 implementation of the above approach # Function to count all pairs # with equal set bits count def totalPairs(arr, n): # dictionary to store count of elements # with equal number of set bits m = dict () for i in range (n): # inbuilt function that returns the # count of set bits of the number x = bin (arr[i]).count( '1' ) m[x] = m.get(x, 0 ) + 1 ; result = 0 for it in m: # there can be (n*(n-1)/2) unique two- # element pairs to choose from n elements result + = (m[it] * (m[it] - 1 )) / / 2 return result # Driver code arr = [ 7 , 5 , 3 , 9 , 1 , 2 ] n = len (arr) print (totalPairs(arr, n)) # This code is contributed by mohit kumar |
C#
// C# program to rearrange a string so that all same // characters become atleast d distance away using System; using System.Collections.Generic; class GFG { /* Function to get no of set bits in binary representation of passed binary no. */ static int countSetBits( int n) { int count = 0; while (n > 0) { n &= (n - 1) ; count++; } return count; } // Function to count all pairs // with equal set bits count static int totalPairs( int []arr, int n) { // map to store count of elements // with equal number of set bits Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0 ; i < n; i++) { // function that returns the // count of set bits of the number int count = countSetBits(arr[i]); if (mp.ContainsKey(count)) { var val = mp[count]; mp.Remove(count); mp.Add(count, val + 1); } else { mp.Add(count, 1); } } int result = 0; foreach (KeyValuePair< int , int > entry in mp){ int values = entry.Value; // there can be (n*(n-1)/2) unique two- // element pairs to choose from n elements result += ((values * (values -1)) / 2); } return result; } // Driver code public static void Main (String[] args) { int []arr = { 7, 5, 3, 9, 1, 2 }; int n = arr.Length; Console.WriteLine(totalPairs(arr, n)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript implementation of above approach /* Function to get no of set bits in binary representation of passed binary no. */ function countSetBits(n) { var count = 0; while (n > 0) { n &= (n - 1) ; count++; } return count; } // Function to count all pairs // with equal set bits count function totalPairs(arr, n) { // map to store count of elements // with equal number of set bits var m = new Map(); for ( var i = 0; i < n; i++) { // inbuilt function that returns the // count of set bits of the number if (m.has(arr[i])) { m.set(countSetBits(arr[i]), m.get(countSetBits(arr[i]))+1); } else { m.set(countSetBits(arr[i]), 1); } } var result = 0; m.forEach((value, key) => { // there can be (n*(n-1)/2) unique two- // element pairs to choose from n elements result += parseInt(key * (key - 1) / 2); }); return result; } // Driver code var arr = [7, 5, 3, 9, 1, 2 ]; var n = arr.length; document.write( totalPairs(arr, n)); </script> |
Output
4
Time Complexity: O(n log n), where n is the number of elements in given array
Auxiliary Space: O(n)
Contact Us