Problem Link:
Practice
Contest
Author: murugappan_s
Testers: sdssudhu,msv99999
Editorialist: murugappan_s
DIFFICULTY: Medium-Hard
PREREQUISITES: Math, Sieve
PROBLEM:
There is an array of size N. We have to make all the elements in the array equal. In one step you can select a particular index idx from the array and do one of the following.
- Replace array[idx] by array[idx]*x where x is any prime number.
- Replace array[idx] by array[idx]/y where y is any prime divisor of array[idx](if exists).
Find out the minimum number of steps required to make all the elements of the array equal.
CONSTRAINTS:
- 1≤N≤100000
- 1≤array[i]≤100000
SOLUTION:
Making all the numbers equal indirectly points to making prime factorization of each and every element in the array equal. If we observe carefully, we can find that one prime factor/number doesn’t affect the other prime factors.
For example if we have two numbers 12( ( 2^2 ) * 3) and 18(2 * ( 3^3 ) ), balancing prime factor 2 doesn’t affect prime factor 3.
So the problem boils down to balancing each and every prime factor in minimum number of steps \text{"independently"}.
Let’s create a new list for each and every prime number in the range [2,100000], wherein each list contains the exponent of them for the prime factorization of each element in the array.
For example consider the array to be [3, 10, 12, 16, 8], the list of 2 contains [0(\text{from 3}), 1(\text{from 10}), 2(\text{from 12}), 4(\text{from 16}), 3(\text{from 8})]. So the problem can be rephrased for each and every list as follows
We have an array, where we are allowed to increase an element’s value by 1 or decrease it by 1. Find the minimum number of steps required to make all elements in the array same.
We have to solve the above rephrased problem for each and every prime number. We can observe that increasing an element by 1 in the rephrased problem indicates multiplication by that prime number in the original problem and decreasing an element by 1 in the rephrased problem indicates division by that prime number(which is a factor) in the original problem.
The rephrased problem is a well known problem and the median of the array is the best target value which minimizes the number of steps taken.Resource1:Median
But won’t the memory be O(X*N) and time be O(X*N*\log(N)) (sorting each list to find median)? Where X is the number of prime numbers in the range [2,100000].
If we observe carefully, the distinct prime factors with non-zero exponents in the prime factorization of any number in the range [1,100000] is at-most 6, because product of even first 7 prime numbers exceed 100000. This implies each number contributes only to at-most 6 lists. So out of the X*N memory only 6*N is non-zero and the rest are zero. So instead of storing each and every zero separately, we can have a counter for zero for each list separately. So time and memory are well within the accepted bounds.
UPD: Prime factorization of a number Q can be done in O(log(Q)) time.Resource2
Time Complexity: O(N*\log(N) + X(\text{Prime Numbers In The Specified Range}))
Space Complexity: O(N)