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 pairsvoid 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 codeint 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 twoimport 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 pairsstatic 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 2def 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 pairsfunction 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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
