Hacer que todos los números de una array sean iguales

Dada una array arr[] , la tarea es hacer que todos los elementos de la array sean iguales a la operación dada. En una sola operación, cualquier elemento de la array se puede multiplicar por 2 o por 3 . Si es posible hacer que todos los elementos de la array sean iguales a la operación dada, imprima Sí ; de lo contrario, imprima No.

Ejemplos: 

Entrada: arr[] = {50, 75, 100} 
Salida: Sí 
{50 * 2 * 3, 75 * 2 * 2, 100 * 3} = {300, 300, 300}

Entrada: arr[] = {10, 14} 
Salida: No 

Enfoque: cualquier número entero positivo se puede factorizar y escribir como 2 ^a * 3 ^b * 5 ^c * 7 ^d * ….. 
Podemos multiplicar números dados por 2 y 3 para poder aumentar a y b por ellos. Así que podemos igualar todos a y b aumentándolos al mismo valor grande (por ejemplo, 100). Pero no podemos cambiar las potencias de otros números primos, por lo que deben ser iguales desde el principio. Podemos verificarlo sumergiendo todos los números de la entrada por dos y por tres tantas veces como sea posible. Entonces todos ellos deben ser iguales.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if all
// the array elements can be made equal
// with the given operation
bool EqualNumbers(int a[], int n)
{
    for (int i = 0; i < n; i++) {
 
        // Divide number by 2
        while (a[i] % 2 == 0)
            a[i] /= 2;
 
        // Divide number by 3
        while (a[i] % 3 == 0)
            a[i] /= 3;
 
        if (a[i] != a[0]) {
            return false;
        }
    }
 
    return true;
}
 
// Driver code
int main()
{
    int a[] = { 50, 75, 150 };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    if (EqualNumbers(a, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of above approach
class GFG
{
 
    // Function that returns true if all
    // the array elements can be made equal
    // with the given operation
    static boolean EqualNumbers(int a[], int n)
    {
        for (int i = 0; i < n; i++)
        {
 
            // Divide number by 2
            while (a[i] % 2 == 0)
            {
                a[i] /= 2;
            }
 
            // Divide number by 3
            while (a[i] % 3 == 0)
            {
                a[i] /= 3;
            }
 
            if (a[i] != a[0])
            {
                return false;
            }
        }
 
        return true;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = {50, 75, 150};
 
        int n = a.length;
 
        if (EqualNumbers(a, n))
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    }
}
 
// This code is contributed by Rajput-JI

# Python3 implementation of the approach
 
# Function that returns true if all
# the array elements can be made equal
# with the given operation
def EqualNumbers(a, n):
 
    for i in range(0, n):
 
        # Divide number by 2
        while a[i] % 2 == 0:
            a[i] //= 2
 
        # Divide number by 3
        while a[i] % 3 == 0:
            a[i] //= 3
 
        if a[i] != a[0]:
            return False
 
    return True
 
# Driver code
if __name__ == "__main__":
 
    a = [50, 75, 150]
    n = len(a)
 
    if EqualNumbers(a, n):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by Rituraj Jain

// C# implementation of above approach
using System;
 
class GFG
{
 
    // Function that returns true if all
    // the array elements can be made equal
    // with the given operation
    static bool EqualNumbers(int []a, int n)
    {
        for (int i = 0; i < n; i++)
        {
 
            // Divide number by 2
            while (a[i] % 2 == 0)
            {
                a[i] /= 2;
            }
 
            // Divide number by 3
            while (a[i] % 3 == 0)
            {
                a[i] /= 3;
            }
 
            if (a[i] != a[0])
            {
                return false;
            }
 
        }
 
        return true;
    }
 
    // Driver code
    public static void Main()
    {
        int []a = {50, 75, 150};
 
        int n = a.Length;
 
        if (EqualNumbers(a, n))
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}
 
// This code is contributed by Ryuga

<?php
// PHP implementation of the approach
// Function that returns true if all
// the array elements can be made equal
// with the given operation
 
function EqualNumbers($a, $n)
{
    for ($i = 0; $i < $n; $i++)
    {
 
        // Divide number by 2
        while ($a[$i] % 2 == 0)
            $a[$i] /= 2;
 
        // Divide number by 3
        while ($a[$i] % 3 == 0)
            $a[$i] /= 3;
 
        if ($a[$i] != $a[0])
        {
            return false;
        }
    }
 
    return true;
}
 
    // Driver code
    $a = array(50, 75, 150 );
    $n = sizeof($a) / sizeof($a[0]);
    if (EqualNumbers($a, $n))
        echo "Yes";
    else
        echo "No";
 
#This code is contributed by ajit..
?>

<script>
 
// Javascript implementation of above approach
 
// Function that returns true if all
// the array elements can be made equal
// with the given operation
function EqualNumbers(a, n)
{
    for(let i = 0; i < n; i++)
    {
         
        // Divide number by 2
        while (a[i] % 2 == 0)
        {
            a[i] = parseInt(a[i] / 2, 10);
        }
 
        // Divide number by 3
        while (a[i] % 3 == 0)
        {
            a[i] = parseInt(a[i] / 3, 10); 
        }
 
        if (a[i] != a[0])
        {
            return false;
        }
    }
    return true;
}
 
// Driver code
let a = [ 50, 75, 150 ];
let n = a.length;
 
if (EqualNumbers(a, n))
{
    document.write("Yes");
}
else
{
    document.write("No");
}
 
// This code is contributed by divyeshrabadiya07  
 
</script>

Yes

Complejidad del tiempo: O(nlog ₂ m + nlog ₃ m)

Espacio Auxiliar: O(1)