We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

I found the problem super easy and I feel like this is a good solution using Java. Does anyone know if I missed something or messed up the time complexity? It appears to be O((m+n)*i)

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int maxA = 0;
int minB = 101;
int[] a = new int[n];
for(int a_i=0; a_i < n; a_i++){
int tmp = in.nextInt();
maxA = tmp > maxA ? tmp:maxA;
a[a_i] = tmp;
}
int[] b = new int[m];
for(int b_i=0; b_i < m; b_i++){
int tmp = in.nextInt();
minB = tmp < minB ? tmp:minB;
b[b_i] = tmp;
}
int integersBetween = 0;
intCheck:
for(int i = maxA; i <= minB; i += maxA)
{
//Check if all A are a factor of i
for(int num : a)
{
if(i%num != 0)
{
continue intCheck;
}
}
//Check if i is a factor of all B
for(int num : b)
{
if(num%i != 0)
{
continue intCheck;
}
}
integersBetween++;
}
System.out.println(integersBetween);
}

I've updated my code for better readability: I guees this will explain it a lot better.

importjava.io.*;importjava.util.*;importjava.text.*;importjava.math.*;importjava.util.regex.*;publicclassSolution{privatebooleancanADivideI(inti,int[]a,intn){booleananswer=false;for(intj=0;j<n;j++){if(i%a[j]==0){if(j==n-1){answer=true;}}else{j=n;}}returnanswer;}privatebooleancanIDivideB(inti,int[]b,intm){booleananswer=false;for(intk=0;k<m;k++){if(b[k]%i==0){if(k==m-1){answer=true;}}else{k=m;}}returnanswer;}publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);Solutions=newSolution();intn=in.nextInt();intm=in.nextInt();int[]a=newint[n];intmax=100,min=0,elementsFound=0;for(inta_i=0;a_i<n;a_i++){a[a_i]=in.nextInt();//Look for Max in A and set that as the MIN if(min<a[a_i]){min=a[a_i];}}int[]b=newint[m];for(intb_i=0;b_i<m;b_i++){b[b_i]=in.nextInt();//Look for Min in B and set that as the MAXif(max>b[b_i]){max=b[b_i];}}for(inti=min;i<=max;i++){if(s.canADivideI(i,a,n)&&s.canIDivideB(i,b,m)){elementsFound++;}}System.out.println(elementsFound);}}

I did something simmilar, I guess it is an optimized version.

importjava.io.*;importjava.util.*;importjava.text.*;importjava.math.*;importjava.util.regex.*;publicclassSolution{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();intm=in.nextInt();int[]a=newint[n];intmax=100,min=0,answr=0;for(inta_i=0;a_i<n;a_i++){a[a_i]=in.nextInt();//Look for Max in A and set that as the MIN if(min<a[a_i]){min=a[a_i];}}int[]b=newint[m];for(intb_i=0;b_i<m;b_i++){b[b_i]=in.nextInt();//Look for Min in B and set that as the MAXif(max>b[b_i]){max=b[b_i];}}for(inti=min;i<=max;i++){for(intj=0;j<n;j++){if(i%a[j]==0){if(j==n-1){for(intk=0;k<m;k++){if(b[k]%i==0){if(k==m-1){answr++;}}else{k=m;}}}}else{j=n;}}}System.out.println(answr);}}

I know it's been a long time since you asked this question, and I apologize for not being active here for a while. But if you are still interested, Here is my answer:

Min and Max are the Maximum value in A and Minimum value in B respectively - Why I chose min from A and max from B you ask? If you think about the question, we need to find element X that can be divided by any A[i] and can divide any B[i]. So logically the number lies between Max(A) and Min(B), the minimum number would be min - Maximum in A and the the maximum number would be max - Minimum in B.

The For loop only needs to be run through those numbers - even though the limit is 0 <= a[i],b[i] <= 100. As the numbers we care about are only the ones present in the set {min,...,max} inclusive.

I know it's been a long time since you asked this question, and I apologize for not being active here for a while. But if you are still interested, Here is my answer:

The for loop before this statement finds that the Element I is divisible by all the elements in array A, a[j]. Thus at any given point if any element a[j] cannot divide I, it should shut off and move on to the next element I + 1.

How do we know if all the elements in array A actually were able to divide I? - If you are still in the loop, and your j is n-1, meaning, you've reached the last element in array A (As the n is the length of A), all the elements at position (J==n-1) satisfied the division (otherwise, the loop would've exited - See j = n in else condition - that is exit logic).

Now if all a[j] were satisfying, we need to check if the element I can divide all elements in B, b[k]. The same logic used in checking if all elements in B are divisible by I - meaning if (K==m-1) where m is length of B - All elements at position m-1 were divisible by I.

At this point we found our element - So answer = answer + 1.

## Between Two Sets

You are viewing a single comment's thread. Return to all comments →

I found the problem super easy and I feel like this is a good solution using Java. Does anyone know if I missed something or messed up the time complexity? It appears to be O((m+n)*i)

EDIT - 1:

I've updated my code for better readability: I guees this will explain it a lot better.

I did something simmilar, I guess it is an optimized version.

Can you explain a bit the algorithm behind the second part of your code works? ( for(int i = min; i <= max; i++){}) Thank you!

I know it's been a long time since you asked this question, and I apologize for not being active here for a while. But if you are still interested, Here is my answer:

Min and Max are the Maximum value in A and Minimum value in B respectively - Why I chose min from A and max from B you ask? If you think about the question, we need to find element X that can be divided by any A[i] and can divide any B[i]. So logically the number lies between Max(A) and Min(B), the minimum number would be min - Maximum in A and the the maximum number would be max - Minimum in B.

The For loop only needs to be run through those numbers - even though the limit is 0 <= a[i],b[i] <= 100. As the numbers we care about are only the ones present in the set {min,...,max} inclusive.

can somebody please Explain this part to me?

if(j == n-1){ for(int k = 0; k < m; k++){ if(b[k]%i == 0){ if(k == m-1){ answr++; } }

I know it's been a long time since you asked this question, and I apologize for not being active here for a while. But if you are still interested, Here is my answer:

The for loop before this statement finds that the Element I is divisible by all the elements in array A, a[j]. Thus at any given point if any element a[j] cannot divide I, it should shut off and move on to the next element I + 1.

How do we know if all the elements in array A actually were able to divide I? - If you are still in the loop, and your j is n-1, meaning, you've reached the last element in array A (As the n is the length of A), all the elements at position (J==n-1) satisfied the division (otherwise, the loop would've exited - See j = n in else condition - that is exit logic).

Now if all a[j] were satisfying, we need to check if the element I can divide all elements in B, b[k]. The same logic used in checking if all elements in B are divisible by I - meaning if (K==m-1) where m is length of B - All elements at position m-1 were divisible by I.

At this point we found our element - So answer = answer + 1.

All is good. but, possibly its good practice to eliminate imagining min or max.

for this

// set the first value of array as min or max then start //comparing from next element

b[0] = in.nextInt(); minB = b[0];

// then

for(int b_i = 1; b_i < m ; b_i++ ) { int tmp = in.nextInt(); minB = tmp < minB ? tmp:minB; b[b_i] = tmp; }

:)

I found similar solution but used the min value from b to loop: