Número de pares cuyo producto es una potencia de 2

Dada una array arr[] que consta de N enteros, la tarea es contar el número total de pares de elementos de la array de la array dada de modo que arr[i] * arr[j] sea la potencia de 2 .

Ejemplos:

Entrada: arr[] = {2, 4, 7, 2}
Salida: 3
Explicación:
arr[0] * arr[1] = 8
arr[0] * arr[3] = 4
arr[1] * arr[3 ] = 8

Entrada: arr[] = {8, 1, 12, 4, 2}
Salida: 6

Enfoque: La idea se basa en el hecho de que un número es una potencia de 2 si contiene solo 2 como su factor primo . Por lo tanto, todos sus divisores son también una potencia de 2 . Siga los pasos a continuación para resolver el problema:

1. Recorre la array dada .
2. Para cada elemento de la array, compruebe si es una potencia de 2 o no . Aumentar el recuento de tales elementos.
3. Finalmente, imprima (cuenta * (cuenta – 1)) / 2 como la cuenta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count pairs having
// product equal to a power of 2
int countPairs(int arr[], int N)
{
    // Stores count of array elements
    // which are power of 2
    int countPowerof2 = 0;
 
    for (int i = 0; i < N; i++) {
 
        // If array element contains
        // only one set bit
        if (__builtin_popcount(arr[i]) == 1)
 
            // Increase count of
            // powers of 2
            countPowerof2++;
    }
 
    // Count required number of pairs
    int desiredPairs
        = (countPowerof2
           * (countPowerof2 - 1))
          / 2;
 
    // Print the required number of pairs
    cout << desiredPairs << ' ';
}
 
// Driver Code
int main()
{
    // Given array
    int arr[4] = { 2, 4, 7, 2 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countPairs(arr, N);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
// Function to count pairs having
// product equal to a power of 2
static void countPairs(int arr[],
                       int N)
{
  // Stores count of array elements
  // which are power of 2
  int countPowerof2 = 0;
 
  for (int i = 0; i < N; i++)
  {
    // If array element contains
    // only one set bit
    if (Integer.bitCount(arr[i]) == 1)
 
      // Increase count of
      // powers of 2
      countPowerof2++;
  }
 
  // Count required number of pairs
  int desiredPairs = (countPowerof2 *
                     (countPowerof2 - 1)) / 2;
 
  // Print the required number of pairs
  System.out.print(desiredPairs + " ");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array
  int arr[] = {2, 4, 7, 2};
 
  // Size of the array
  int N = arr.length;
 
  // Function Call
  countPairs(arr, N);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to count pairs having
# product equal to a power of 2
def countPairs(arr, N):
     
    # Stores count of array elements
    # which are power of 2
    countPowerof2 = 0
 
    for i in range(N):
 
        # If array element contains
        # only one set bit
        if (bin(arr[i]).count('1') == 1):
 
            # Increase count of
            # powers of 2
            countPowerof2 += 1
 
    # Count required number of pairs
    desiredPairs = (countPowerof2 *
                   (countPowerof2 - 1)) // 2
 
    # Print the required number of pairs
    print(desiredPairs)
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [ 2, 4, 7, 2 ]
 
    # Size of the array
    N = len(arr)
 
    # Function call
    countPairs(arr, N)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
using System.Linq;
 
class GFG{
 
// Function to count pairs having
// product equal to a power of 2
static void countPairs(int []arr,
                       int N)
{
     
    // Stores count of array elements
    // which are power of 2
    int countPowerof2 = 0;
     
    for(int i = 0; i < N; i++)
    {
         
        // If array element contains
        // only one set bit
        if ((Convert.ToString(
             arr[i], 2)).Count(
             f => (f == '1')) == 1)
              
            // Increase count of
            // powers of 2
            countPowerof2++;
    }
     
    // Count required number of pairs
    int desiredPairs = (countPowerof2 *
                       (countPowerof2 - 1)) / 2;
     
    // Print the required number of pairs
    Console.WriteLine(desiredPairs + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 2, 4, 7, 2 };
     
    // Size of the array
    int N = arr.Length;
     
    // Function call
    countPairs(arr, N);
}
}
 
// This code is contributed by math_lover

<script>
// Javascript program for the
// above approach
 
// Function to count pairs having
// product equal to a power of 2
function countPairs(arr,N)
{
    // Stores count of array elements
  // which are power of 2
  let countPowerof2 = 0;
  
  for (let i = 0; i < N; i++)
  {
    // If array element contains
    // only one set bit
    if (Number(arr[i].toString(2).split("").sort().join("")).toString().length == 1)
  
      // Increase count of
      // powers of 2
      countPowerof2++;
  }
  
  // Count required number of pairs
  let desiredPairs = (countPowerof2 *
                     (countPowerof2 - 1)) / 2;
  
  // Print the required number of pairs
  document.write(desiredPairs + " ");
}
 
// Driver Code
// Given array
let arr=[2, 4, 7, 2];
// Size of the array
let N = arr.length;
 
// Function Call
countPairs(arr, N);
 
 
// This code is contributed by patel2127
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)