PROBLEM LINK:
MIN OPERATION
Author: alpha_1205
Tester: anert
Editorialist:anert
DIFFICULTY:
Cakewalk
PROBLEM:
You are given two arrays, namely a and b, of size n. Your task is to find the minimum possible steps to convert a such that the smallest integer in array a divides all elements of array b. In each step you can delete any single element of array a which was not previously removed. If it is not possible to convert array a into required array then print -1.
Prerequisites:
- Knowledge of Euclidian algorithm for calculation of the greatest common divisor.
- Basic array manipulation.
- Sorting algorithms.
- Pinch of common sense
Hint:
- You have to find a number which is a divisor of all elements of array b.
- Try finding GCD of all elements of array b.
QUICK EXPLAINATION:
You will have to find the gcd of array b using Euclidian algorithm. Then you will have to sort array a in ascending order. After that, you will have to check whether the smallest element of array a divides the gcd of array b. If it fails to do so, we will remove it. We will increment the counter by one for each removal. We will print the value of counter.
Explanation:
We can solve this problem by using greedy strategy. We will find the GCD of array B using Euclid’s GCD algorithm*. We will now sort array A in ascending order and then check whether any element in array A divides the GCD of array B. Suppose any a [i] where, 1 <= i <= n divides the GCD of B, proves that it will divide the whole array B. So, we have to delete the first (i-1) components of the sorted array A.
*Euclid’s GCD algorithm:
It is a greedy algorithm in which we, generally, use recursive function to calculate gcd of two integers. We continuously find remainder of number, say x, when divided by y and if it is 0, we return x, otherwise we call the function again.
Pseudocode:
def gcd(x,y):
if(y==0):
return x
return gcd(x,x%y)
The time complexity of this algorithm O (log (min (x,y))) and for and array it is O (log (maximum element of array)). So the overall time complexity is:
O (nlog (n) + nlog (maximum (b[i]))
This will satisfy our constraints.
Setter’s solution
import java.util.Scanner;
import java.util.*;
import java.util.Arrays;
public class Main{
public static int gcd(int a,int b){
int max = Math.max(a,b);
int min = Math.min(a,b);
a = max;
b = min;
if(b == 0){
return a;
}
else return gcd(b,a%b);
}
public static int gcdarray(int[]arr){
int g = arr[0];
for(int i = 0;i<arr.length;i++){
g = gcd(arr[i],g);
}
return g;
}
public static void main(String[]args){
Scanner at = new Scanner(System.in);
Random rand = new Random();
int t = at.nextInt();
while(t-->0){
int n = at.nextInt();
int[]a = new int[n];
int[]b = new int[n];
for(int i = 0;i<n;i++){
a[i] = at.nextInt();
}
for(int i = 0;i<n;i++){
b[i] = at.nextInt();
}
Arrays.sort(a);
int gcd = gcdarray(b);
boolean ok = false;
for(int i = 0;i<n;i++){
if(gcd % a[i] == 0){
System.out.println(i);
ok = true;
break;
}
}
if(!ok){
System.out.println(-1);
}
}
}
}
Tester’s Solution
/**
* @file gcd.cpp
* @author Aniruddh Modi
* @brief
* This is testers' solution.
* @version 0.1
* @date 2022-02-19
*
* @copyright Kaha se lagaenge 😂
*
*/
#include<bits/stdc++.h>
using namespace std;
int arr_gcd(int arr[],int n){
int x=arr[0];
for(int i=1;i<n;i++){
x = __gcd(x,arr[i]);
}
return x;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr1[n],arr2[n];
for(int i=0;i<n;i++){
cin>>arr1[i];
}
for(int i=0;i<n;i++){
cin>>arr2[i];
}
sort(arr1,arr1+n);
bool f=1;
int ct=0,gcd = arr_gcd(arr2,n);
for(int i=0;i<n;i++){
if((gcd%arr1[i])==0){
cout<<ct<<endl;
f=0;
break;
}
ct++;
}
if(f) cout<<-1<<endl;
}
return 0;
}
Solution in python
def gcd(x,y):
if (y == 0):
return x
else:
return gcd (y, x % y)
def arr_gcd(l,n):
g = 0
for i in range(n):
g = gcd(g,l[i])
return g
def main():
t = int(input())
while t>0:
t-=1
n=int(input())
l1 = list(map(int,input().strip().split()))[:n]
l2 = list(map(int,input().strip().split()))[:n]
g = arr_gcd(l2,n)
l1.sort()
for i in range(n):
if(g%l1[i]==0):
print(i)
print("\n")
break
else:
print(-1)
print("\n")
return 0
main()