Given an array arr[], the task is to count all the valid pairs from the array. A pair (arr[i], arr[j]) is said to be valid if func( arr[i] ) + func( arr[j] ) = func( XOR(arr[i], arr[j]) ) where func(x) returns the number of set bits in x.
Examples:
Input: arr[] = {2, 3, 4, 5, 6}
Output: 3
(2, 4), (2, 5) and (3, 4) are the only valid pairs.Input: arr[] = {12, 13, 34, 25, 6}
Output: 4
Approach: Iterating every possible pair and check whether the pair satisfies the given condition. If the condition is satisfied then update count = count + 1. Print the count in the end.
Algorithm:
1. The setBits function takes an integer n as input and returns the number of set bits (i.e., bits with a value of 1) in its binary representation. It does this by initializing a variable count to 0 and then repeatedly performing the following steps as long as n is not 0:
a. Subtracting 1 from n and performing a bitwise AND operation with the original value of n.
b. Incrementing count by 1.
2. The idea behind this function is that each iteration of the loop removes the rightmost set bit in n, so the loop will continue until all set bits have been removed, and the number of iterations (i.e., the value of count) will be equal to the number of set bits in n.
3. The countPairs function takes an array a of integers and its length n as input, and returns the number of pairs of elements in the array that satisfy a certain condition. It does this by initializing a variable count to 0 and then iterating over all pairs of elements in the array, checking if the condition is satisfied for each pair:
a. For each pair of elements, it calls the setBits function to compute the number of set bits in each element, and the number of set bits in the XOR of the two elements.
b. It then checks if the sum of the number of set bits in the two elements is equal to the number of set bits in their XOR.
c. If the condition is satisfied, it increments count by 1.
4. The setBits function is used in the countPairs function to compute the number of set bits in integers. It does this by repeatedly removing the rightmost set bit in the input integer until all set bits have been removed, and counting the number of times this operation is performed.
5. The countPairs function uses two nested loops to iterate over all pairs of elements in the array, and computes the number of set bits in each element and in their XOR using the setBits function. It then checks if the sum of the number of set bits in the two elements is equal to the number of set bits in their XOR. If the condition is satisfied, it increments the count of pairs.
6. The function returns the total count of pairs that satisfy the condition.
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 number// of set bits in nint setBits(int n){ int count = 0; while (n) { n = n & (n - 1); count++; } return count;}// Function to return the count of required pairsint countPairs(int a[], int n){ int count = 0; for (int i = 0; i < n - 1; i++) { // Set bits for first element of the pair int setbits_x = setBits(a[i]); for (int j = i + 1; j < n; j++) { // Set bits for second element of the pair int setbits_y = setBits(a[j]); // Set bits of the resultant number which is // the XOR of both the elements of the pair int setbits_xor_xy = setBits(a[i] ^ a[j]); // If the condition is satisfied if (setbits_x + setbits_y == setbits_xor_xy) // Increment the count count++; } } // Return the total count return count;}// Driver codeint main(){ int a[] = { 2, 3, 4, 5, 6 }; int n = sizeof(a) / sizeof(a[0]); cout << countPairs(a, n);} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function to return the number// of set bits in nstatic int setBits(int n){ int count = 0; while (n > 0) { n = n & (n - 1); count++; } return count;}// Function to return the count of // required pairsstatic int countPairs(int a[], int n){ int count = 0; for (int i = 0; i < n - 1; i++) { // Set bits for first element // of the pair int setbits_x = setBits(a[i]); for (int j = i + 1; j < n; j++) { // Set bits for second element // of the pair int setbits_y = setBits(a[j]); // Set bits of the resultant number which is // the XOR of both the elements of the pair int setbits_xor_xy = setBits(a[i] ^ a[j]); // If the condition is satisfied if (setbits_x + setbits_y == setbits_xor_xy) // Increment the count count++; } } // Return the total count return count;} // Driver code public static void main (String[] args) { int []a = { 2, 3, 4, 5, 6 }; int n = a.length; System.out.println(countPairs(a, n)); }}// This code is contributed by ajit. |
Python3
# Python 3 implementation of the approach# Function to return the number# of set bits in ndef setBits(n): count = 0 while (n): n = n & (n - 1) count += 1 return count# Function to return the count# of required pairsdef countPairs(a, n): count = 0 for i in range(0, n - 1, 1): # Set bits for first element # of the pair setbits_x = setBits(a[i]) for j in range(i + 1, n, 1): # Set bits for second element # of the pair setbits_y = setBits(a[j]) # Set bits of the resultant number # which is the XOR of both the # elements of the pair setbits_xor_xy = setBits(a[i] ^ a[j]); # If the condition is satisfied if (setbits_x + setbits_y == setbits_xor_xy): # Increment the count count += 1 # Return the total count return count# Driver codeif __name__ == '__main__': a = [2, 3, 4, 5, 6] n = len(a) print(countPairs(a, n))# This code is contributed by# Sanjit_Prasad |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the number// of set bits in nstatic int setBits(int n){ int count = 0; while (n > 0) { n = n & (n - 1); count++; } return count;}// Function to return the count of // required pairsstatic int countPairs(int []a, int n){ int count = 0; for (int i = 0; i < n - 1; i++) { // Set bits for first element // of the pair int setbits_x = setBits(a[i]); for (int j = i + 1; j < n; j++) { // Set bits for second element // of the pair int setbits_y = setBits(a[j]); // Set bits of the resultant number which is // the XOR of both the elements of the pair int setbits_xor_xy = setBits(a[i] ^ a[j]); // If the condition is satisfied if (setbits_x + setbits_y == setbits_xor_xy) // Increment the count count++; } } // Return the total count return count;}// Driver codepublic static void Main(){ int []a = { 2, 3, 4, 5, 6 }; int n = a.Length; Console.Write(countPairs(a, n));}}// This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the approach// Function to return the number// of set bits in nfunction setBits($n){ $count = 0; while ($n) { $n = $n & ($n - 1); $count++; } return $count;}// Function to return the count of // required pairsfunction countPairs(&$a, $n){ $count = 0; for ($i = 0; $i < $n - 1; $i++) { // Set bits for first element // of the pair $setbits_x = setBits($a[$i]); for ($j = $i + 1; $j < $n; $j++) { // Set bits for second element of the pair $setbits_y = setBits($a[$j]); // Set bits of the resultant number which is // the XOR of both the elements of the pair $setbits_xor_xy = setBits($a[$i] ^ $a[$j]); // If the condition is satisfied if ($setbits_x + $setbits_y == $setbits_xor_xy) // Increment the count $count++; } } // Return the total count return $count;}// Driver code$a = array(2, 3, 4, 5, 6 );$n = sizeof($a) / sizeof($a[0]);echo countPairs($a, $n);// This code is contributed by ita_c?> |
Javascript
<script>// Javascript implementation of the approach // Function to return the number// of set bits in nfunction setBits(n){ let count = 0; while (n > 0) { n = n & (n - 1); count++; } return count;}// Function to return the count of // required pairsfunction countPairs(a, n){ let count = 0; for(let i = 0; i < n - 1; i++) { // Set bits for first element // of the pair let setbits_x = setBits(a[i]); for(let j = i + 1; j < n; j++) { // Set bits for second element // of the pair let setbits_y = setBits(a[j]); // Set bits of the resultant number which is // the XOR of both the elements of the pair let setbits_xor_xy = setBits(a[i] ^ a[j]); // If the condition is satisfied if (setbits_x + setbits_y == setbits_xor_xy) // Increment the count count++; } } // Return the total count return count;}// Driver codelet a = [ 2, 3, 4, 5, 6 ];let n = a.length;document.write(countPairs(a, n));// This code is contributed by unknown2108</script> |
3
Complexity Analysis:
- Time Complexity: O(N2logM), where N is the size of the given array and M is the maximum element in the array.
- Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
