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 nunsigned int countSetBits(int n){ unsigned int count = 0; while (n) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsint 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 codeint 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 approachclass GFG {// Function to return the count// of set bits in nstatic int countSetBits(int n){ int count = 0; while (n > 0) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsstatic 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 codepublic 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 nfunction countSetBits(n){ var count = 0; while (n > 0) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsfunction 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 codevar 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> |
Output:
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 nunsigned int countSetBits(int n){ unsigned int count = 0; while (n) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsint 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 codeint 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 approachimport java.util.*;class GFG { static int MAX = 32;// Function to return the count// of set bits in nstatic int countSetBits(int n){ int count = 0; while (n > 0) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsstatic 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 codepublic 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 = 4print (pairs(arr, n, k)) # This code is contributed by CrazyPro |
C#
// C# implementation of the approachusing System; class GFG { static int MAX = 32;// Function to return the count// of set bits in nstatic int countSetBits(int n){ int count = 0; while (n > 0) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsstatic 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 codepublic 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 approachvar MAX = 32;// Function to return the count// of set bits in nfunction countSetBits(n){ var count = 0; while (n > 0) { n &= (n - 1); count++; } return count;}// Function to return the count// of required pairsfunction 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 codevar 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> |
Output:
1
Time complexity: O(MAX2)
Auxiliary Space: O(MAX)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
