Count pairs with set bits sum equal to K
Given an array arr[] and an integer K, the task is to count the pairs whose sum of set bits is K
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 4
Output: 1
(3, 5) is the only valid pair as the count
of set bits in the integers {1, 2, 3, 4, 5}
are {1, 1, 2, 1, 2} respectively.
Input: arr[] = {5, 42, 35, 22, 7}, K = 6
Output: 6
Naive approach: Initialise count = 0 and run two nested loops and check all possible pairs and check whether the sum of count bits is K. If yes then increment count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of set bits in n unsigned int countSetBits( int n) { unsigned int count = 0; while (n) { n &= (n - 1); count++; } return count; } // Function to return the count // of required pairs int pairs( int arr[], int n, int k) { // To store the count int count = 0; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Sum of set bits in both the integers int sum = countSetBits(arr[i]) + countSetBits(arr[j]); // If current pair satisfies // the given condition if (sum == k) count++; } } return count; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 4; cout << pairs(arr, n, k); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the count // of set bits in n static int countSetBits( int n) { int count = 0 ; while (n > 0 ) { n &= (n - 1 ); count++; } return count; } // Function to return the count // of required pairs static int pairs( int arr[], int n, int k) { // To store the count int count = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { // Sum of set bits in both the integers int sum = countSetBits(arr[i]) + countSetBits(arr[j]); // If current pair satisfies // the given condition if (sum == k) count++; } } return count; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int n = arr.length; int k = 4 ; System.out.println(pairs(arr, n, k)); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to return the count # of set bits in n def countSetBits(n) : count = 0 ; while (n) : n & = (n - 1 ); count + = 1 return count; # Function to return the count # of required pairs def pairs(arr, n, k) : # To store the count count = 0 ; for i in range (n) : for j in range (i + 1 , n) : # Sum of set bits in both the integers sum = countSetBits(arr[i]) + countSetBits(arr[j]); # If current pair satisfies # the given condition if ( sum = = k) : count + = 1 ; return count; # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 ]; n = len (arr); k = 4 ; print (pairs(arr, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; public class GFG { // Function to return the count // of set bits in n static int countSetBits( int n) { int count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } // Function to return the count // of required pairs static int pairs( int []arr, int n, int k) { // To store the count int count = 0; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Sum of set bits in both the integers int sum = countSetBits(arr[i]) + countSetBits(arr[j]); // If current pair satisfies // the given condition if (sum == k) count++; } } return count; } // Driver code public static void Main(String []args) { int []arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; int k = 4; Console.WriteLine(pairs(arr, n, k)); } } // This code is contributed by Princi Singh |
Javascript
<script> // javascript implementation of the approach // Function to return the count // of set bits in n function countSetBits(n) { var count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } // Function to return the count // of required pairs function pairs(arr , n , k) { // To store the count var count = 0; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Sum of set bits in both the integers var sum = countSetBits(arr[i]) + countSetBits(arr[j]); // If current pair satisfies // the given condition if (sum == k) count++; } } return count; } // Driver code var arr = [ 1, 2, 3, 4, 5 ]; var n = arr.length; var k = 4; document.write(pairs(arr, n, k)); // This code contributed by shikhasingrajput </script> |
1
Time complexity: O(n2logn)
Auxiliary Space: O(1)
Efficient approach: Assume that every integer can be represented using 32 bits, create a frequency array freq[] of size 32 where freq[i] will store the count of numbers having set bits equal to i. Now run two nested loops on this frequency array, if i + j = K then count of pairs will be freq[i] * freq[j] for all such i and j.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 32 // Function to return the count // of set bits in n unsigned int countSetBits( int n) { unsigned int count = 0; while (n) { n &= (n - 1); count++; } return count; } // Function to return the count // of required pairs int pairs( int arr[], int n, int k) { // To store the count int count = 0; // Frequency array int f[MAX + 1] = { 0 }; for ( int i = 0; i < n; i++) f[countSetBits(arr[i])]++; for ( int i = 0; i <= MAX; i++) { for ( int j = i; j <= MAX; j++) { // If current pair satisfies // the given condition if (i + j == k) { // (arr[i], arr[i]) cannot be a valid pair if (i == j) count += ((f[i] * (f[i] - 1)) / 2); else count += (f[i] * f[j]); } } } return count; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 4; cout << pairs(arr, n, k); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { static int MAX = 32 ; // Function to return the count // of set bits in n static int countSetBits( int n) { int count = 0 ; while (n > 0 ) { n &= (n - 1 ); count++; } return count; } // Function to return the count // of required pairs static int pairs( int arr[], int n, int k) { // To store the count int count = 0 ; // Frequency array int []f = new int [MAX + 1 ]; for ( int i = 0 ; i < n; i++) f[countSetBits(arr[i])]++; for ( int i = 0 ; i <= MAX; i++) { for ( int j = i; j <= MAX; j++) { // If current pair satisfies // the given condition if (i + j == k) { // (arr[i], arr[i]) cannot be a valid pair if (i == j) count += ((f[i] * (f[i] - 1 )) / 2 ); else count += (f[i] * f[j]); } } } return count; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int n = arr.length; int k = 4 ; System.out.println(pairs(arr, n, k)); } } // This code is contributed by Rajput-Ji |
Python3
# Python implementation of the approach MAX = 32 # Function to return the count # of set bits in n def countSetBits(n) : count = 0 ; while (n): n & = (n - 1 ); count + = 1 ; return count; # Function to return the count # of required pairs def pairs(arr, n, k): # To store the count count = 0 ; # Frequency array f = [ 0 for i in range ( MAX + 1 )] for i in range (n): f[countSetBits(arr[i])] + = 1 ; for i in range ( MAX + 1 ): for j in range ( 1 , MAX + 1 ): # If current pair satisfies # the given condition if (i + j = = k): # (arr[i], arr[i]) cannot be a valid pair if (i = = j): count + = ((f[i] * (f[i] - 1 )) / 2 ); else : count + = (f[i] * f[j]); return count; # Driver code arr = [ 1 , 2 , 3 , 4 , 5 ] n = len (arr) k = 4 print (pairs(arr, n, k)) # This code is contributed by CrazyPro |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 32; // Function to return the count // of set bits in n static int countSetBits( int n) { int count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } // Function to return the count // of required pairs static int pairs( int []arr, int n, int k) { // To store the count int count = 0; // Frequency array int []f = new int [MAX + 1]; for ( int i = 0; i < n; i++) f[countSetBits(arr[i])]++; for ( int i = 0; i <= MAX; i++) { for ( int j = i; j <= MAX; j++) { // If current pair satisfies // the given condition if (i + j == k) { // (arr[i], arr[i]) cannot be a valid pair if (i == j) count += ((f[i] * (f[i] - 1)) / 2); else count += (f[i] * f[j]); } } } return count; } // Driver code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; int k = 4; Console.WriteLine(pairs(arr, n, k)); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // javascript implementation of the approach var MAX = 32; // Function to return the count // of set bits in n function countSetBits(n) { var count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } // Function to return the count // of required pairs function pairs(arr , n , k) { // To store the count var count = 0; // Frequency array var f = Array.from({length: MAX + 1}, (_, i) => 0); for (i = 0; i < n; i++) f[countSetBits(arr[i])]++; for (i = 0; i <= MAX; i++) { for (j = i; j <= MAX; j++) { // If current pair satisfies // the given condition if (i + j == k) { // (arr[i], arr[i]) cannot be a valid pair if (i == j) count += ((f[i] * (f[i] - 1)) / 2); else count += (f[i] * f[j]); } } } return count; } // Driver code var arr = [ 1, 2, 3, 4, 5 ]; var n = arr.length; var k = 4; document.write(pairs(arr, n, k)); // This code contributed by Princi Singh </script> |
1
Time complexity: O(MAX2)
Auxiliary Space: O(MAX)