DIVIDEMAKEEQ - Editorial

editorial
, ,
1

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++ and math.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))
1 Like
2 
void solve(){
    int n;
    cin>>n;
    vector<int> v(n);
    input(v);

    int gcd = v[0];
    for(auto i : v) gcd = __gcd(gcd,i);

    if(gcd == 1){
        cout<<n<<endl;
        return;
    }

    int cnt = 0;
    for(auto i : v){
        if(i != gcd) cnt++;
    }
    cout<<cnt<<endl;
}

can anyone tell me why this code don’t work instead I have change the condition to i==gcd and print answer as n - cnt

3

Consider this testcase:

n=3
1 1 1

here the gcd is 1 but all the elements are same, so no need to perform any operation.
but your code prints 3.

1 Like
4

Thank u . This test case actually was not think at the time of completion. I appreciate your effort. cool :fire:

6 
import sys
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd, deque, Counter
from heapq import merge, heapify, heappop, heappush, nsmallest
from itertools import combinations
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log

# input str
def inp():
    return sys.stdin.readline().strip()

# input int
def iinp():
    return int(inp())

# map and array of int
def mp():
    return map(int, inp().split())

# array of int
def liinp():
    return list(mp())

# array of string/char
def lmps():
    return list(map(str, inp()))
    
# --------------------------------------
def solve(n, T):
    T.sort()
    idx = bl(T, T[0]+1)
    
    ans = 0
    for i in range(idx, n):
        if T[i]%T[0]==0:
            ans += 1
        else:
            return n
    return ans
    
# --------------- main() ---------------
if __name__ == '__main__':
    tc = iinp()
    
    for _ in range(tc):
        n = iinp()
        T = liinp()
        print(solve(n, T))

Here is my code and this too pass all tests.