Cuente los pares en una array de modo que un elemento sea el poder de otro

Dada una array arr[] , la tarea es contar los pares en la array de modo que un elemento sea la potencia de otro en cada par.
Ejemplos: 
 

Input: arr[] = {16, 2, 3, 9}
Output: 2
The 2 pairs are (16, 2) and (3, 9)

Input: arr[] = {2, 3, 5, 7}
Output: 0

Acercarse: 
 

• Después de tomar la array como entrada, primero debemos encontrar todos los pares posibles en esa array .
• Entonces, averigüe los pares de la array.
• Luego, para cada par, comprueba si un elemento es potencia de otro. Si es así, aumente el conteo requerido en uno.
• Cuando se hayan verificado todos los pares, devuelva o imprima el conteo de dicho par.

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

// C++ program to count pairs in array
// such that one element is power of another
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if given number number y
// is power of x
bool isPower(int x, int y)
{
    // log function to calculate value
    int res1 = log(y) / log(x);
    double res2 = log(y) / log(x);
 
    // compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Function to find pairs from array
int countPower(int arr[], int n)
{
    int res = 0;
 
    // Iterate through all pairs
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
 
            // Increment count if one is
            // the power of other
            if (isPower(arr[i], arr[j])
                || isPower(arr[j], arr[i]))
                res++;
 
    return res;
}
 
// Driver code
int main()
{
    int a[] = { 16, 2, 3, 9 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << countPower(a, n);
    return 0;
}

// Java program to count pairs in array
// such that one element is power of another
 
class GFG
{
 
    // Function to check if given number number y
    // is power of x
    static boolean isPower(int x, int y)
    {
        // log function to calculate value
        int res1 = (int)(Math.log(y) / Math.log(x));
        double res2 = Math.log(y) / Math.log(x);
     
        // compare to the result1
        // or result2 both are equal
        return (res1 == res2);
    }
     
    // Function to find pairs from array
    static int countPower(int arr[], int n)
    {
        int res = 0;
     
        // Iterate through all pairs
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
     
                // Increment count if one is
                // the power of other
                if (isPower(arr[i], arr[j])
                    || isPower(arr[j], arr[i]))
                    res++;
     
        return res;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int a[] = { 16, 2, 3, 9 };
        int n =a.length;
        System.out.println(countPower(a, n));
    }
 
}
 
// This code is contributed by AnkitRai01

# Python3 program to count pairs in array
# such that one element is power of another
 
from math import log
 
# Function to check if given number number y
# is power of x
def isPower(x, y) :
 
    # log function to calculate value
    res1 = log(y) // log(x);
    res2 = log(y) / log(x);
     
    # compare to the result1
    # or result2 both are equal
    return (res1 == res2);
 
# Function to find pairs from array
def countPower( arr, n) :
     
    res = 0;
     
    # Iterate through all pairs
    for i in range(n) :
        for j in range(i + 1, n) :
            # Increment count if one is
            # the power of other
            if isPower(arr[i], arr[j]) or isPower(arr[j], arr[i]) :
                res += 1;
 
    return res;
 
# Driver code
if __name__ == "__main__" :
     
    a = [ 16, 2, 3, 9 ];
    n = len(a);
     
    print(countPower(a, n));
 
# This code is contributed by AnkitRai01

// C# program to count pairs in array
// such that one element is power of another
 
using System;
 
public class GFG
{
 
    // Function to check if given number number y
    // is power of x
    static bool isPower(int x, int y)
    {
        // log function to calculate value
        int res1 = (int)(Math.Log(y) / Math.Log(x));
        double res2 = Math.Log(y) / Math.Log(x);
     
        // compare to the result1
        // or result2 both are equal
        return (res1 == res2);
    }
     
    // Function to find pairs from array
    static int countPower(int []arr, int n)
    {
        int res = 0;
     
        // Iterate through all pairs
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
     
                // Increment count if one is
                // the power of other
                if (isPower(arr[i], arr[j])
                    || isPower(arr[j], arr[i]))
                    res++;
     
        return res;
    }
     
    // Driver code
    public static void Main ()
    {
        int []a = { 16, 2, 3, 9 };
        int n =a.Length;
        Console.WriteLine(countPower(a, n));
    }
 
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript program to count pairs in array
// such that one element is power of another
 
// Function to check if given number number y
// is power of x
function isPower(x, y)
{
    // log function to calculate value
    var res1 = parseInt(Math.log(y) / Math.log(x));
    var res2 = Math.log(y) / Math.log(x);
 
    // compare to the result1
    // or result2 both are equal
    return (res1 == res2);
}
 
// Function to find pairs from array
function countPower(arr, n)
{
    var res = 0;
 
    // Iterate through all pairs
    for (var i = 0; i < n; i++)
        for (var j = i + 1; j < n; j++)
 
            // Increment count if one is
            // the power of other
            if (isPower(arr[i], arr[j])
                || isPower(arr[j], arr[i]))
                res++;
 
    return res+1;
}
 
// Driver code
var a = [ 16, 2, 3, 9 ];
var n = a.length;
document.write(countPower(a, n));
 
// This code is contributed by rutvik_56.
 
</script>

2

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(1)