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

  • sagar1108 + 8 comments
    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];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        int[] b = new int[m];
        for(int b_i=0; b_i < m; b_i++){
            b[b_i] = in.nextInt();
        }
        Arrays.sort(a);
        Arrays.sort(b);
        int min = a[0];
        int max = b[b.length-1];
        int count=0;
        //System.out.println(max+" "+min);
        for(int i=min;i<=max;i++){
            if(hasFactors(i,a) && isFactor(i,b)){
                count++;
            }
        }
        System.out.println(count);
    }
    
    public static boolean hasFactors(int num, int[] arr){
        for(int i=0;i<arr.length;i++){
            if(num%arr[i]!=0){
                return false;
            }
        }
        return true;
    }
    
    public static boolean isFactor(int num, int[] arr){
        for(int i=0;i<arr.length;i++){
            if(arr[i]%num!=0){
                return false;
            }
        }
        return true;
    }
}
    • itaravin + 0 comments

      Thanks for the answer...... helped me to find out logic :)

    • 1m0l0rh3 + 1 comment

      Similar to my solution. Can't it be solved with a shorter, more elegant logic though?

      • ScienceD + 1 comment

        What do you think about recursive approach? I think its better code. For such small array sizes its not that much slower.

        int between(vector < int > a, vector < int > b, int x){
    if(x <= 100)
    {
        bool good_x = true;
        for(int i = 0; i < a.size(); ++i)
            good_x &= x%a[i] == 0;
        for(int i = 0; i < b.size(); ++i)
            good_x &= b[i]%x == 0;
        return good_x + between(a, b, x+1);
    }
    else
        return 0;
}
    • em_f1 + 0 comments

      This is almost exactly what I did! A small optimization thing I did was to do "i += min" instead of "i++". Since you know that the next number has to be at least a multiple of that number. I don't know if I'm being clear or not haha

    • jdfurlan + 1 comment

      Thanks for this solution! I realized that int i=min;i<=max;i++ iterates all the way to the highest value in b, which is unnecessary, as the largest possible factor of values in array b is the smallest value in it. Change int max = b[b.length-1]; to int max = b[0]; and you save a lot of unnecessary work.

      • Abii12 + 1 comment

        The solution is very much helpful!!But "x" has to lie between the max value in array a and min value in arra y b.hence the values of min and max could be int min=a[a.length-1] and int max = b[0];This will reduce the time for processing the code.

        • jdfurlan + 1 comment

          This is true just tested. So ideal range is int min = a[a.length-1]; int max = b[0];

          • Abii12 + 0 comments

            :) :)

    • celik55 + 1 comment

      is arrays.sort() needed? you can find min and max while reading inputs.

      • jdfurlan + 1 comment

        You're right! I've optimized my solution and removed the sorting, nice! Now min always holds the the highest value in a, and max holds the lowest in b.

        	int min = 0;
    	int max = Integer.MAX_VALUE;
	for (int a_i = 0; a_i < n; a_i++) {
            int x = in.nextInt();
			if(x > min) min = x;
            a[a_i] = x;
            
		}
		int[] b = new int[m];
		for (int b_i = 0; b_i < m; b_i++) {
            int x = in.nextInt();
			if(x < max) max = x;
            b[b_i] = x;
		}
        • ryanfehr18 + 1 comment

          no reason to make max Integer.MAX_VALUE when problem constraints put the max at 100, simply put it at 101

          • jdfurlan + 0 comments

            This is true and demonstrates good understanding of the problem constraints. In terms of memory usage however, I believe 2^32 bits are allocated for every integer, regardless of size. The unsused bits are just set to 0's.

    • thong1411998 + 0 comments

      Could you explain why you figure this out ? The code is easy to understrand but I can't come up with this idea

    • 1RV15EC129 + 0 comments

      i tried the same way in c++ but i was getting time out erreoe

    • LamaO3 + 0 comments

      Man , that is awesome