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

Given an integer array A consisting of N integers. In one move, we can choose any index i ( 0 ≤ i ≤ N-1) and divide it either by 2 or 3(the number A[i] should be divisible by 2 or 3, respectively), the task is to find the minimum number of total moves required such that all array elements are equal. If it is not possible to make all elements equal, print -1.

Examples:

Input: N = 3, A[] = [1, 4, 3]
Output: 3
Explanation: Divide A[1] by 2 twice and A[2] by 3 once. Hence a minimum of 3 moves are required.

Input: N = 3, A[] = [2, 7, 6]
Output: -1
Explanation: It is not possible to make all array elements equal.

Approach: To solve the problem follow the below idea:

First, let’s factorize each A[i] in the form of 3^p*2^q*z. Now it is easy to see that if for any i, j if the values z_i and z_j are not equal, then it is impossible to make all the array elements equal. In this case, return -1 as the answer. Otherwise, we can calculate the sum of all p and q over all elements and print that as the answer.

Steps that were to follow the above approach: 

• Let us find the gcd g of the whole array and divide all numbers by g so that we have all the other factors other than 2 or 3 separated.
• Initialize a variable ans = 0 which will store the total number of moves required to make all elements equal. 
• For each A[i], divide it by 2 till A[i] is divisible by 2 and increment ans = ans + 1.
• Now, repeat the above process, but this time divide it by 3.
• Print the final answer as ans.

Below is the code to implement the above approach:

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

Given an integer array A consisting of N integers. In one move, we can choose any index i ( 0 ≤ i ≤ N-1) and divide it either by 2 or 3(the number A[i] should be divisible by 2 or 3, respectively), the task is to find the minimum number of total moves required such that all array elements are equal. If it is not possible to make all elements equal, print -1.

Examples:

Input: N = 3, A[] = [1, 4, 3]
Output: 3
Explanation: Divide A[1] by 2 twice and A[2] by 3 once. Hence a minimum of 3 moves are required.

Input: N = 3, A[] = [2, 7, 6]
Output: -1
Explanation: It is not possible to make all array elements equal.

Approach: To solve the problem follow the below idea:

First, let’s factorize each A[i] in the form of 3^p*2^q*z. Now it is easy to see that if for any i, j if the values z_i and z_j are not equal, then it is impossible to make all the array elements equal. In this case, return -1 as the answer. Otherwise, we can calculate the sum of all p and q over all elements and print that as the answer.

Steps that were to follow the above approach: 

• Let us find the gcd g of the whole array and divide all numbers by g so that we have all the other factors other than 2 or 3 separated.
• Initialize a variable ans = 0 which will store the total number of moves required to make all elements equal. 
• For each A[i], divide it by 2 till A[i] is divisible by 2 and increment ans = ans + 1.
• Now, repeat the above process, but this time divide it by 3.
• Print the final answer as ans.

Below is the code to implement the above approach:

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