Encuentre si es posible hacer que todos los elementos de una array sean iguales mediante las operaciones dadas

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 3 o por 5 cualquier número de veces. 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[] = {18, 30, 54, 90, 162} 
Salida: Sí 
Explicación: 
Podemos realizar las siguientes operaciones: 
162 X 5 = 810 
90 X 3 X 3 = 810 
54 X 5 X 3 = 810 
30 X 3 X 3 X 3 = 810 
18 X 5 X 3 X 3 = 810
Entrada: arr[] = {18, 36, 58, 90, 162} 
Salida: No 
Explicación: 
No hay manera de hacer que todos los elementos sean iguales. 
 

Observaciones : 
 

• Si después de algunas operaciones, todos los números se igualan, tendrán la misma factorización prima, es decir, cada número tendrá la misma potencia de 2, 3, 5… y así sucesivamente.
• Dado que estamos multiplicando los números solo por 3 y 5 , que son números primos , podemos hacer que las potencias de 3 y 5 en la descomposición en factores primos de todos los números sean iguales después de algunas operaciones.
• Por lo tanto, para que todos los números sean iguales, las potencias de los Números Primos en la descomposición en factores primos que no sean 3 y 5 deben ser iguales.
• La solución sería tomar cada número y quitarle todas las potencias de 3 y 5 . Si luego todos los números resultan ser iguales, entonces es posible hacer que los elementos de la array sean iguales usando las operaciones dadas; de lo contrario, no es posible.

Pasos : 
 

1. Divida cada elemento de la array arr[] con 3 y 5 de modo que toda la potencia de 3 y 5 en la factorización prima de cada elemento se convierta en cero.
2. Compruebe si todos los elementos de la array son iguales o no. En caso afirmativo, escriba Sí.
3. De lo contrario imprima No.

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

// C++ implementation to find if it's
// possible to make all elements of an
// array equal by using two operations.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find if it's possible
// to make all array elements equal
bool canMakeEqual(int a[], int n)
{
    // Iterate over all numbers
    for (int i = 0; i < n; i++) {
 
        // If a number has a power of 5
        // remove it
        while (a[i] % 5 == 0) {
            a[i] /= 5;
        }
 
        // If a number has a power of 3
        // remove it
        while (a[i] % 3 == 0) {
            a[i] /= 3;
        }
    }
 
    int last = a[0];
 
    // Check if all elements are equal
    // in the final array
    for (int i = 1; i < n; i++) {
        if (a[i] != last) {
            return false;
        }
    }
 
    return true;
}
 
// Driver's Code
int main()
{
    int arr[] = { 18, 30, 54, 90, 162 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to check if all
    // element in the array can be equal
    // or not.
    if (canMakeEqual(arr, n)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
 
    return 0;
}

// Java implementation to find if it's
// possible to make all elements of an
// array equal by using two operations.
class GFG{
  
// Function to find if it's possible
// to make all array elements equal
static boolean canMakeEqual(int a[], int n)
{
    // Iterate over all numbers
    for (int i = 0; i < n; i++) {
  
        // If a number has a power of 5
        // remove it
        while (a[i] % 5 == 0) {
            a[i] /= 5;
        }
  
        // If a number has a power of 3
        // remove it
        while (a[i] % 3 == 0) {
            a[i] /= 3;
        }
    }
  
    int last = a[0];
  
    // Check if all elements are equal
    // in the final array
    for (int i = 1; i < n; i++) {
        if (a[i] != last) {
            return false;
        }
    }
  
    return true;
}
  
// Driver's Code
public static void main(String[] args)
{
    int arr[] = { 18, 30, 54, 90, 162 };
  
    int n = arr.length;
  
    // Function call to check if all
    // element in the array can be equal
    // or not.
    if (canMakeEqual(arr, n)) {
        System.out.print("YES" +"\n");
    }
    else {
        System.out.print("NO" +"\n");
    }
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation to find if it's
# possible to make all elements of an
# array equal by using two operations.
 
# Function to find if it's possible
# to make all array elements equal
def canMakeEqual( a, n) :
 
    # Iterate over all numbers
    for i in range(n) :
 
        # If a number has a power of 5
        # remove it
        while (a[i] % 5 == 0) :
            a[i] //= 5;
         
        # If a number has a power of 3
        # remove it
        while (a[i] % 3 == 0) :
            a[i] //= 3;
 
    last = a[0];
 
    # Check if all elements are equal
    # in the final array
    for i in range(1,n) :
        if (a[i] != last) :
            return False;
 
    return True;
 
# Driver's Code
if __name__ == "__main__" :
 
    arr = [ 18, 30, 54, 90, 162 ];
 
    n = len(arr);
 
    # Function call to check if all
    # element in the array can be equal
    # or not.
    if (canMakeEqual(arr, n)) :
        print("YES");
     
    else :
        print("NO");
 
# This code is contributed by AnkitRai01

// C# implementation to find if it's
// possible to make all elements of an
// array equal by using two operations.
using System;
 
class GFG{
 
// Function to find if it's possible
// to make all array elements equal
static bool canMakeEqual(int []a, int n)
{
    // Iterate over all numbers
    for (int i = 0; i < n; i++) {
  
        // If a number has a power of 5
        // remove it
        while (a[i] % 5 == 0) {
            a[i] /= 5;
        }
  
        // If a number has a power of 3
        // remove it
        while (a[i] % 3 == 0) {
            a[i] /= 3;
        }
    }
  
    int last = a[0];
  
    // Check if all elements are equal
    // in the final array
    for (int i = 1; i < n; i++) {
        if (a[i] != last) {
            return false;
        }
    }
  
    return true;
}
  
// Driver's Code
public static void Main(string[] args)
{
    int []arr = { 18, 30, 54, 90, 162 };
  
    int n = arr.Length;
  
    // Function call to check if all
    // element in the array can be equal
    // or not.
    if (canMakeEqual(arr, n)) {
        Console.WriteLine("YES");
    }
    else {
        Console.WriteLine("NO");
    }
}
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation to find if it's
// possible to make all elements of an
// array equal by using two operations.   
// Function to find if it's possible
    // to make all array elements equal
    function canMakeEqual(a , n) {
        // Iterate over all numbers
        for (i = 0; i < n; i++) {
 
            // If a number has a power of 5
            // remove it
            while (a[i] % 5 == 0) {
                a[i] /= 5;
            }
 
            // If a number has a power of 3
            // remove it
            while (a[i] % 3 == 0) {
                a[i] /= 3;
            }
        }
 
        var last = a[0];
 
        // Check if all elements are equal
        // in the final array
        for (i = 1; i < n; i++) {
            if (a[i] != last) {
                return false;
            }
        }
 
        return true;
    }
 
    // Driver's Code
     
        var arr = [ 18, 30, 54, 90, 162 ];
 
        var n = arr.length;
 
        // Function call to check if all
        // element in the array can be equal
        // or not.
        if (canMakeEqual(arr, n)) {
            document.write("YES" + "\n");
        } else {
            document.write("NO" + "\n");
        }
 
// This code contributed by umadevi9616
</script>

YES

Complejidad de tiempo: O(N), donde N es el tamaño de la array.

Complejidad espacial : O(1)