Make parts of Array equal by repeatedly dividing parts by 2 or 3

Given an integer array A consisting of N integers. In a single transfer, we will select any index i ( 0 ≤ i ≤ N-1) and divide it both by 2 or 3(the quantity A[i] ought to be divisible by 2 or 3, respectively), the duty is to search out the minimal quantity of complete strikes required such that every one array parts are equal. If it isn’t attainable to make all parts equal, print -1.

Examples:

Enter: N = 3, A[] = [1, 4, 3]
Output: 3
Rationalization: Divide A[1] by 2 twice and A[2] by 3 as soon as. Therefore a minimal of three strikes are required.

Enter: N = 3, A[] = [2, 7, 6]
Output: -1
Rationalization: It’s not attainable to make all array parts equal.

Strategy: To resolve the issue observe the beneath concept:

First, let’s factorize every A[i] within the type of 3^p*2^q*z. Now it’s simple to see that if for any i, j if the values z_i and z_j are usually not equal, then it’s unattainable to make all of the array parts equal. On this case, return -1 as the reply. In any other case, we will calculate the sum of all p and q over all parts and print that as the reply.

Steps that had been to observe the above strategy: 

• Allow us to discover the gcd g of the entire array and divide all numbers by g in order that we’ve got all the opposite components apart from 2 or 3 separated.
• Initialize a variable ans = 0 which can retailer the full variety of strikes required to make all parts equal. 
• For every A[i], divide it by 2 until A[i] is divisible by 2 and increment ans = ans + 1.
• Now, repeat the above course of, however this time divide it by 3.
• Print the ultimate reply as ans.

Under is the code to implement the above strategy:

Time Complexity: O(N*max(logA[i]))
Auxiliary House: O(1)