Make components of Array equal by repeatedly dividing components 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 each one array components are equal. If it isn’t attainable to make all components equal, print -1.
Enter: N = 3, A = [1, 4, 3]
Rationalization: Divide A by 2 twice and A by 3 as soon as. Therefore a minimal of three strikes are required.
Enter: N = 3, A = [2, 7, 6]
Rationalization: It isn’t attainable to make all array components equal.
Strategy: To unravel the issue comply with the beneath concept:
First, let’s factorize every A[i] within the type of 3p*2q*z. Now it’s simple to see that if for any i, j if the values zi and zj aren’t equal, then it’s unimaginable to make all of the array components 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 components and print that as the reply.
Steps that have been to comply with the above method:
- Allow us to discover the gcd g of the entire array and divide all numbers by g in order that now we have all the opposite elements aside from 2 or 3 separated.
- Initialize a variable ans = 0 which is able to retailer the entire variety of strikes required to make all components 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.
Beneath is the code to implement the above method:
Time Complexity: O(N*max(logA[i]))
Auxiliary Area: O(1)