Programa Php para Pares tales que uno es un múltiplo de potencia de otro

Se le da una array A[] de n elementos y un entero positivo k (k > 1). Ahora tiene que encontrar el número de pares Ai, Aj tales que Ai = Aj*(k ^x ) donde x es un número entero. 
Nota: (Ai, Aj) y (Aj, Ai) deben contarse una vez.
Ejemplos: 
 

Input : A[] = {3, 6, 4, 2},  k = 2
Output : 2
Explanation : We have only two pairs 
(4, 2) and (3, 6)

Input : A[] = {2, 2, 2},   k = 2
Output : 3
Explanation : (2, 2), (2, 2), (2, 2) 
that are (A1, A2), (A2, A3) and (A1, A3) are 
total three pairs where Ai = Aj * (k^0) 

Para resolver este problema, primero ordenamos la array dada y luego para cada elemento Ai, encontramos un número de elementos igual al valor Ai * k^x para diferentes valores de x hasta que Ai * k^x es menor o igual que el mayor de Ai. 
Algoritmo: 
 

    // sort the given array
    sort(A, A+n);

    // for each A[i] traverse rest array
    for (int i=0; i ≤ n-1; i++)
    {
        for (int j=i+1; j ≤ n-1; j++)
        {
            // count Aj such that Ai*k^x = Aj
            int x = 0;

            // increase x till Ai * k^x ≤ 
            // largest element
            while ((A[i]*pow(k, x)) ≤ A[j])
            {
                if ((A[i]*pow(k, x)) == A[j])
                {              
                     ans++;
                     break;
                }
                x++;
            }        
        }   
    }
    // return answer
    return ans;

<?php
// PHP Program to find pairs count
 
// function to count
// the required pairs
function countPairs($A, $n, $k)
{
$ans = 0;
 
// sort the given array
sort($A);
 
// for each A[i]
// traverse rest array
for ($i = 0; $i < $n; $i++)
{
    for ($j = $i + 1; $j < $n; $j++)
    {
 
    // count Aj such that Ai*k^x = Aj
    $x = 0;
 
    // increase x till Ai *
    // k^x <= largest element
    while (($A[$i] * pow($k, $x)) <= $A[$j])
    {
        if (($A[$i] * pow($k, $x)) == $A[$j])
        {
        $ans++;
        break;
        }
        $x++;
    }
    }
}
return $ans;
}
 
// Driver Code
 
$A = array(3, 8, 9, 12, 18,
              4, 24, 2, 6);
$n = count($A);
$k = 3;
echo countPairs($A, $n, $k);
 
// This code is contributed by anuj_67.
?>

6

Complejidad de tiempo: O(n*n), ya que se utilizan bucles anidados
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional

¡ Consulte el artículo completo sobre Pares tales que uno es un múltiplo de potencia del otro para obtener más detalles!