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.
Loading...
  1. Practice
  2. Algorithms
  3. Implementation
  4. Between Two Sets
  5. Discussions

Between Two Sets

  • ryanfehr18 + 3 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)

    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);
}
    • yash3shah + 2 comments

      EDIT - 1:

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

      import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    private boolean canADivideI(int i, int[] a, int n){
        boolean answer = false;
        for(int j=0;j<n;j++){
                if(i%a[j] == 0){
                    if(j==n-1){
                        answer = true;
                    }
                }
                else{j=n;}
        }
        return answer;
    }
    
    private boolean canIDivideB(int i, int[] b, int m){
        boolean answer = false;
        for(int k=0;k<m;k++){
            if(b[k]%i ==0){
                if(k==m-1){
                    answer = true;
                }
            }
            else {k=m;}
        }   
        return answer;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Solution s = new Solution();
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        int max = 100, min = 0, elementsFound = 0;
        for(int a_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 = new int[m];
        for(int b_i=0; b_i < m; b_i++){
            b[b_i] = in.nextInt();
            //Look for Min in B and set that as the MAX
            if(max > b[b_i]) {max = b[b_i];}
        }
        for(int i = 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.

      import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        int max = 100, min = 0, answr = 0;
        for(int a_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 = new int[m];
        for(int b_i=0; b_i < m; b_i++){
            b[b_i] = in.nextInt();
            //Look for Min in B and set that as the MAX
            if(max > b[b_i]) {max = b[b_i];}
        }
        for(int i = min; i <= max; i++){
            for(int j = 0; j < n; j++){
                if(i%a[j] == 0){
                    if(j == n-1){
                        for(int k = 0; k < m; k++){
                            if(b[k]%i == 0){
                                if(k == m-1){
                                    answr++;
                                }
                            }
                            else {k = m;}
                        }
                    }
                }
                else{j = n;}
            }
        }
        System.out.println(answr);
    }
}
      • joyshurock + 1 comment

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

        • yash3shah + 0 comments

          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.

      • Arpit7694 + 1 comment

        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++; } }

        • yash3shah + 0 comments

          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.

    • dev_kchs + 0 comments

      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; }

      :)

    • romulo8000 + 0 comments

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

      static int getTotalX(int[] a, int[] b) {
    int result = 0;
    int min = IntStream.of(b).min().getAsInt();

    outer:
    for ( int j = 1; j <= min; j++ ) {
        for (int i : b) {
        	if (i % j != 0) {
            	continue outer;
            }
       	}

        for (int i : a) {
    	    if (j % i != 0) {
            	continue outer;
            }
        }

        result++;
	}

    return result;
}