Count Pairs in an Array with Equal Set Bits in C++

We are given an array of integer type elements and the task is to form the pairs from the given array and calculate the set bits of elements in the pair and check whether both the elements are having equal number of set bits or not.

Set bits in a binary number is represented by 1. Whenever we calculate the binary number of an integer value then it is formed as the combination of 0’s and 1’s. So, the digit 1 is known as set bit in the terms of the computer.

Input 

int arr[] = {6, 5, 1, 3, 7}

Output 

Count of pairs in an array such that both elements has equal set bits are: 3

Explanation 

The pairs formed from the given array are-:
(6, 5): 6 -> 2 set bits, 5 -> 2 set bits :(valid pair)
(6, 5): 6 -> 2 set bits, 1 -> 1 set bit:(invalid pair)
(6, 3): 6 -> 2 set bits, 3 -> 2 set bits :(valid pair)
(6, 7): 6 -> 2 set bits, 7 -> 3 set bits :(invalid pair)
(5, 1): 5 -> 2 set bits, 1 -> 1 set bits :(invalid pair)
(5, 3): 5 -> 2 set bits, 3 -> 2 set bits :(valid pair)
(5, 1): 5 -> 2 set bits, 7 -> 3 set bits :(invalid pair)
(1, 3): 1 -> 1 set bits, 3 -> 2 set bits :(invalid pair)
(1, 3): 1 -> 1 set bits, 7 -> 3 set bits :(invalid pair)
(3, 7): 3 -> 2 set bits, 7 -> 3 set bits :(invalid pair)
So, there are 3 valid pairs with equal number of set bits and those are (6, 5), (6, 3) and (5, 2)

Input 

int arr[] = {4, 6, 3, 2}

Output 

Count of pairs in an array such that both elements has equal set bits are: 3

Explanation 

The pairs formed from the given array are-:
(4, 6): 4 -> 1 set bits, 6 -> 2 set bits :(invalid pair)
(4, 3): 4 -> 1 set bits, 3 -> 2 set bits :(invalid pair)
(4, 2): 4 -> 1 set bits, 2 -> 1 set bits :(valid pair)
(6, 3): 6 -> 2 set bits, 3 -> 2 set bits :(valid pair)
(6, 2): 6 -> 2 set bits, 2 -> 1 set bits :(invalid pair)
(3, 2): 3 -> 2 set bits, 2 -> 1 set bits :(invalid pair)
So, there are 2 valid pairs with equal number of set bits and those are (4, 2) and (6, 3).

Approach used in the below program is as follows

• Input an array of integer elements and calculate the size of an array and pass the data to the function

• Declare a temporary variable count to store the count of pairs with the equal number of set bits.

• Start loop FOR from i to 0 till the size of an array

• Inside the loop, start another loop FOR from j to i + 1 till the size of an array

• Inside the loop, set first and second elements of a pair as the total number of set bits by calling the function ‘__builtin_popcount(element)’ that returns the total number of set bits of an integer number.

• Check IF set bits of first and second element of a pair are equal then increment the count by 1

• Return the count

• Print result.

Example

 Live Demo

#include <iostream>
using namespace std;
int pair_setBit(int arr[], int size){
   int count = 0;
   for(int i = 0 ;i <size ; i++){
      for(int j = i+1; j<size; j++){
         int first = __builtin_popcount(arr[i]);
         int second = __builtin_popcount(arr[j]);
         if(first == second){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {6, 5, 1, 3, 7};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of pairs in an array such that both elements has equal set bits are: "<<pair_setBit(arr, size);
   return 0;
}

Output

If we run the above code it will generate the following output −

Count of pairs in an array such that both elements has equal set bits are: 3