Count unordered pairs (i,j) such that product of a[i] and a[j] is power of two
Given an array of N elements. The task is to count unordered pairs (i, j) in the array such that the product of a[i] and a[j] can be expressed as a power of two.
Examples:
Input : arr[] = {2, 3, 4, 8, 10} Output : 3 Explanation: The pair of array element will be (2, 4), (2, 8), (4, 8) whose product are 8, 16, 32 respectively which can be expressed as power of 2, like 2^3, 2^4, 2^5. Input : arr[] = { 2, 5, 8, 16, 128 } Output : 6
If you multiply and and their product become , then z=x*y, now if it’s possible to express as power of two then it can be proved that both and can be expressed as power of two. Basically z= 2a = 2(b+c) = 2b * 2c = x * y, where and both can hold a minimum value 0.
So now we have to count the number of elements in the array which can be expressed as a power of two. If the count is k, then answer will be kC2 = k*(k-1)/2, as we need the count of unordered pairs.
Below is the implementation of above approach:
C++
// C++ program to Count unordered pairs (i, j) // in array such that product of a[i] and a[j] // can be expressed as power of two #include <bits/stdc++.h> using namespace std; /* Function to check if x is power of 2*/ bool isPowerOfTwo( int x) { /* First x in the below expression is for the case when x is 0 */ return x && (!(x&(x-1))); } // Function to Count unordered pairs void Count_pairs( int a[], int n) { int count = 0; for ( int i = 0; i < n; i++) { // is a number can be expressed // as power of two if (isPowerOfTwo(a[i])) count++; } // count total number // of unordered pairs int ans = (count * (count - 1)) / 2; cout << ans << "\n" ; } // Driver code int main() { int a[] = { 2, 5, 8, 16, 128 }; int n = sizeof (a) / sizeof (a[0]); Count_pairs(a, n); return 0; } |
Java
// Java program to Count unordered pairs (i, j) // in array such that product of a[i] and a[j] // can be expressed as power of two import java.io.*; class GFG { /* Function to check if x is power of 2*/ static boolean isPowerOfTwo( int x) { /* First x in the below expression is for the case when x is 0 */ return (x > 0 && (!((x&(x- 1 ))> 0 ))); } // Function to Count unordered pairs static void Count_pairs( int a[], int n) { int count = 0 ; for ( int i = 0 ; i < n; i++) { // is a number can be expressed // as power of two if (isPowerOfTwo(a[i])) count++; } // count total number // of unordered pairs int ans = (count * (count - 1 )) / 2 ; System.out.println( ans); } // Driver code public static void main (String[] args) { int a[] = { 2 , 5 , 8 , 16 , 128 }; int n = a.length; Count_pairs(a, n); } } // This code is contributed // by shs |
Python 3
# Python3 program to Count unordered pairs # (i, j) in array such that product of a[i] # and a[j] can be expressed as power of two # Function to check if x is power of 2 def isPowerOfTwo(x) : # First x in the below expression # is for the case when x is 0 return (x and ( not (x & (x - 1 )))) # Function to Count unordered pairs def Count_pairs(a, n) : count = 0 for i in range (n) : # is a number can be expressed # as power of two if isPowerOfTwo(a[i]) : count + = 1 # count total number # of unordered pairs ans = (count * (count - 1 )) / 2 print (ans) # Driver code if __name__ = = "__main__" : a = [ 2 , 5 , 8 , 16 , 128 ] n = len (a) Count_pairs(a, n) # This code is contributed by ANKITRAI1 |
C#
// C# program to Count unordered pairs (i, j) // in array such that product of a[i] and a[j] // can be expressed as power of two using System; public class GFG{ /* Function to check if x is power of 2*/ static bool isPowerOfTwo( int x) { /* First x in the below expression is for the case when x is 0 */ return (x >0&& (!((x&(x-1))>0))); } // Function to Count unordered pairs static void Count_pairs( int []a, int n) { int count = 0; for ( int i = 0; i < n; i++) { // is a number can be expressed // as power of two if (isPowerOfTwo(a[i])) count++; } // count total number // of unordered pairs int ans = (count * (count - 1)) / 2; Console.WriteLine( ans); } // Driver code static public void Main (){ int []a = { 2, 5, 8, 16, 128 }; int n = a.Length; Count_pairs(a, n); } } // This code is contributed // by Sach_Code |
PHP
<?php // PHP program to Count unordered // pairs (i, j) in array such that // product of a[i] and a[j] can be // expressed as power of two /* Function to check if x is power of 2*/ function isPowerOfTwo( $x ) { /* First x in the below expression is for the case when x is 0 */ return ( $x && (!( $x & ( $x - 1)))); } // Function to Count unordered pairs function Count_pairs( $a , $n ) { $count = 0; for ( $i = 0; $i < $n ; $i ++) { // is a number can be expressed // as power of two if (isPowerOfTwo( $a [ $i ])) $count ++; } // count total number // of unordered pairs $ans = ( $count * ( $count - 1)) / 2; echo $ans , "\n" ; } // Driver code $a = array ( 2, 5, 8, 16, 128 ); $n = sizeof( $a ); Count_pairs( $a , $n ); // This code is contributed // by Sach_code ?> |
Javascript
<script> // JavaScript program to // Count unordered pairs (i, j) // in array such that product of a[i] and a[j] // can be expressed as power of two /* Function to check if x is power of 2*/ function isPowerOfTwo( x) { /* First x in the below expression is for the case when x is 0 */ return (x >0&& (!((x&(x-1))>0))); } // Function to Count unordered pairs function Count_pairs(a,n) { let count = 0; for (let i = 0; i < n; i++) { // is a number can be expressed // as power of two if (isPowerOfTwo(a[i])) count++; } // count total number // of unordered pairs let ans = (count * (count - 1)) / 2; document.write( ans); } // Driver code let a = [ 2, 5, 8, 16, 128 ]; let n = a.length; Count_pairs(a, n); // This code is contributed by sravan kumar </script> |
Output
6
Complexity Analysis:
- Time Complexity: O(N), where N is the number of elements in the array.
- Auxiliary Space: O(1)
Contact Us