PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Vishesh Saraswat
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh
DIFFICULTY:
1185
PREREQUISITES:
Knowledge of GCD
PROBLEM:
You have an array A. In one move you can choose an index i and set A_i \to \frac{A_i}{X} where X is some factor of A_i.
Find the minimum number of moves needed to make all the elements equal.
EXPLANATION:
Suppose we make some moves and end up with all the elements equal, say to an integer y.
Then, notice that y must divide every A_i, since one operation only allows us to replace an element with one of its factors.
Since y must divide every A_i, y must also divide \gcd(A_1, A_2, \ldots, A_N).
Now notice that we might as well choose y = \gcd(A_1, A_2, \ldots, A_N), because:
- It obviously satisfies the condition that it divides every element of A
- It is the largest possible integer that satisfies this condition
This gives a rather simple solution:
- Compute y = \gcd(A_1, \ldots, A_N).
- To do this, first initialize y = A_1. Then, for each i \gt 1, set y = \gcd(y, A_i).
- Computing the gcd of two elements can be done using inbuilt functions, like
std::gcd
in C++ andmath.gcd
in Python.
- Then, for each A_i:
- If A_i = y, we don’t need to change this element at all.
- Otherwise, we need exactly one move to turn A_i into y.
So, count the number of times y appears in the array — let this be k. The answer is then N - k.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
from math import gcd
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for x in a:
g = gcd(x, g)
print(n - a.count(g))