STABLE - Editorial

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)

1 Like

You can use \text{} to render normal text but still make it look LaTeX-ey and ‘important’.

Example:
X( \text{prime numbers in the specified range} )
1\text{ ( from 10 )}
instead of
X(PrimeNumbersInTheSpecifiedRange)
1(from10)

You can also use \log ( $\log$ ) instead of log ( $log$ )

1 Like

Thank you psaini72. I have made the changes, let me know if more changes are required.