Dada una array de N elementos. La tarea es contar pares no ordenados (i, j) en la array de modo que el producto de a[i] y a[j] pueda expresarse como una potencia de dos.
Ejemplos :
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
Si multiplicas 
and 
y su producto se convierte en 
, entonces z=x*y, ahora si es posible expresarlo como potencia de dos, entonces se puede demostrar que ambos y pueden expresarse como potencia de dos. Básicamente z= 2 a = 2 (b+c) = 2 b * 2 c = x * y , donde 
y 
ambos
pueden tener un valor mínimo de 0.
Ahora tenemos que contar la cantidad de elementos en la array que se pueden expresar como una potencia de dos. Si el conteo es k, entonces la respuesta será kC2 = k*(k-1)/2, ya que necesitamos el conteo de pares desordenados.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
6
Complejidad temporal: O(N), donde N es el número de elementos de la array.