Recuento de pares en una array tal que la mayor potencia de 2 que divide su producto es 1

Dada una array arr[] de N enteros positivos. La tarea es encontrar el conteo de pares (arr[i], arr[j]) tal que la máxima potencia de 2 que divide arr[i] * arr[j] sea 1 .
Ejemplos: 
 

Entrada: arr[] = {3, 5, 2, 8} 
Salida: 3 
(3, 2), (5, 2) y (3, 5) son los únicos pares válidos. 
Dado que la potencia de 2 que divide a 3 * 2 = 6 es 1, 
5 * 2 = 10 es 1 y 3 * 5 = 15 es 0.
Entrada: arr[] = {4, 2, 7, 11, 14, 15, 18} 
Salida: 12 
 

Enfoque: como la potencia máxima de 2 que divide arr[i] * arr[j] es como máximo 1 , significa que si P es el producto, entonces  debe ser impar o 2 es el único factor par de P.
Implica que tanto arr[i] como arr[j] deben ser impares o exactamente uno de ellos es par y 2 es el único factor par de este número. 
Si impar es la cuenta de los números impares y par es la cuenta de los números pares tales que 2es el único factor par de ese número, entonces la respuesta será impar * par + impar * (impar – 1) / 2 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of valid pairs
int cntPairs(int a[], int n)
{
 
    // To store the count of odd numbers and
    // the count of even numbers such that 2
    // is the only even factor of that number
    int odd = 0, even = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If current number is odd
        if (a[i] % 2 == 1)
            odd++;
 
        // If current number is even and 2
        // is the only even factor of it
        else if ((a[i] / 2) % 2 == 1)
            even++;
    }
 
    // Calculate total number of valid pairs
    int ans = odd * even + (odd * (odd - 1)) / 2;
 
    return ans;
}
 
// Driver code
int main()
{
 
    int a[] = { 4, 2, 7, 11, 14, 15, 18 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << cntPairs(a, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the count of valid pairs
static int cntPairs(int a[], int n)
{
 
    // To store the count of odd numbers and
    // the count of even numbers such that 2
    // is the only even factor of that number
    int odd = 0, even = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // If current number is odd
        if (a[i] % 2 == 1)
            odd++;
 
        // If current number is even and 2
        // is the only even factor of it
        else if ((a[i] / 2) % 2 == 1)
            even++;
    }
 
    // Calculate total number of valid pairs
    int ans = odd * even + (odd * (odd - 1)) / 2;
 
    return ans;
}
 
// Driver code
public static void main(String []args)
{
    int a[] = { 4, 2, 7, 11, 14, 15, 18 };
    int n = a.length;
 
    System.out.println(cntPairs(a, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function to return the count of valid pairs
def cntPairs(a, n) :
 
    # To store the count of odd numbers and
    # the count of even numbers such that 2
    # is the only even factor of that number
    odd = 0; even = 0;
 
    for i in range(n) :
 
        # If current number is odd
        if (a[i] % 2 == 1) :
            odd += 1;
 
        # If current number is even and 2
        # is the only even factor of it
        elif ((a[i] / 2) % 2 == 1) :
            even += 1;
     
    # Calculate total number of valid pairs
    ans = odd * even + (odd * (odd - 1)) // 2;
 
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 4, 2, 7, 11, 14, 15, 18 ];
    n = len(a);
 
    print(cntPairs(a, n));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to return the count of valid pairs
static int cntPairs(int []a, int n)
{
 
    // To store the count of odd numbers and
    // the count of even numbers such that 2
    // is the only even factor of that number
    int odd = 0, even = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // If current number is odd
        if (a[i] % 2 == 1)
            odd++;
 
        // If current number is even and 2
        // is the only even factor of it
        else if ((a[i] / 2) % 2 == 1)
            even++;
    }
 
    // Calculate total number of valid pairs
    int ans = odd * even + (odd * (odd - 1)) / 2;
 
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    int []a = { 4, 2, 7, 11, 14, 15, 18 };
    int n = a.Length;
 
    Console.WriteLine(cntPairs(a, n));
}
}
 
// This code is contributed by Ajay KUmar

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of valid pairs
function cntPairs(a, n)
{
 
    // To store the count of odd numbers and
    // the count of even numbers such that 2
    // is the only even factor of that number
    var odd = 0, even = 0;
 
    for (var i = 0; i < n; i++) {
 
        // If current number is odd
        if (a[i] % 2 == 1)
            odd++;
 
        // If current number is even and 2
        // is the only even factor of it
        else if ((a[i] / 2) % 2 == 1)
            even++;
    }
 
    // Calculate total number of valid pairs
    var ans = odd * even + (odd * (odd - 1)) / 2;
 
    return ans;
}
 
// Driver code
var a = [4, 2, 7, 11, 14, 15, 18];
var n = a.length;
document.write( cntPairs(a, n));
 
// This code is contributed by rrrtnx.
</script>

12

Complejidad de tiempo: O (n) donde n es el número de elementos en una array dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo 
Espacio auxiliar: O (1), ya que no estamos usando ningún espacio adicional.