Between Two Sets Hackerrank problem solution

                                          

Between Two Sets Hackerrank

To solve the Two sets Hackerrank Problem Consider two sets of positive integers, A={a0,a1,a2,…an-1} and B={b0,b1,b2,…bm-1} and we say that a positive integer ‘x’ is between sets A and B if the following conditions are satisfied:

  • All elements in A are factors of x.
  • x is a factor of all elements in B.
  • Given A and B, find and print the number of integers (i.e., possible x’s) that are between the two sets.

Input Format

  • The first line contains two space-separated integers describing the respective values of n (the number of elements in set A) and m (the number of elements in set B).
  • The second line contains n distinct space-separated integers describing a0,a1,a2,…an-1.
  • The third line contains m distinct space-separated integers describing b0,b1,b2,…bm-1.

 

Constraints

  • 1<=n,m<=10
  • 1<=ai,bi<=100

Output Format

Print the number of integers that are considered to be between A and B.

Sample Input

2 3
2 4
16 32 96
Sample Output

3

Explanation

The integers that are between A and B are 4, 8, and 16.Though this problem can be solved with brute-force, there is a nice fast solution.
– x is divisible by all numbers of A if and only if it is divisible by their least common multiple. Denote it as l.
– All numbers of B are divisible by x if and only if the greatest common divisor of all numbers of B is divisible by B. Denote it as r.
– Now we have to find the number of x such that r is divisible by x and x is divisible by l. If r is not divisible by l, no such x exists. Otherwise, we can divide r, x, and l by l. Now it’s just the number of divisors of (r/l) which can be found in Sqrt(c) time or even faster, where C is the maximum number of the sets.

In this solution, one needs to carefully calculate l as this number could be huge. If l becomes more than C, then we need to stop calculating and say that our answer is zero.

Solution of Between Two Sets Hackerrank problem in C++
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i = 0; i < int(n); ++i)

const int maxc = 100;

int gcd(int a, int b) {
    while (a && b) {
        if (a >= b)
            a %= b;
        else
            b %= a;
    }
    return a + b;
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    int n, m;
    cin >> n >> m;
    int A = 1, B = 0;
    forn (i, n) {
        int x;
        cin >> x;
        A = lcm(A, x);
        if (A > maxc) {
            cout << 0 << '\n';
            return 0;
        }
    }
    forn (i, m) {
        int x;
        cin >> x;
        B = gcd(B, x);
    }
    if (B % A != 0) {
        cout << 0 << '\n';
        return 0;
    }
    B /= A;
    int res = 0;
    for (int i = 1; i * i <= B; ++i) {
        if (B % i == 0) {
            ++res;
            if (i * i != B)
                ++res;
        }
    }
    cout << res << '\n';
}

 

In the above example, the first function of gcd() is used to find the factor of the set A, and then in the second function lcm(), we are retrieving the lcm with the help of gcd found above.

Then, a loop is created so that all the values should be fitted in the set A to and the second loop to create set B.In the next step, checking the condition to be true then it returns 0 else all the above-mentioned process will run.

In the last, we are counting that the multiple of lcm from set A and factors of gcd from set B are equal and how many times.This will return the count to which these are equal.

Solution of Two Sets Hackerrank problem in C++ II
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int maxA(vector<int> a) {
    int maxx = 0;
    for(auto i : a) {
        if(i > maxx)
            maxx = i;
    }
    
    return maxx;
}

int minB(vector<int> b) {
    int minn = 1000000;
    for(auto i : b) {
        if(i < minn)
            minn = i;
    }
    
    return minn;
}

bool checkDivide(int a, int b) {
    if(0 == a % b)
        return true;
    
    return false;
}


int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<int> a(n);
    for(int a_i = 0;a_i < n;a_i++){
       cin >> a[a_i];
    }
    vector<int> b(m);
    for(int b_i = 0;b_i < m;b_i++){
       cin >> b[b_i];
    }
    
    set<int> myset;
    set<int> toremove;
    
    int maxa = maxA(a);
    int minb = minB(b);
    
    for(int t = maxa; t <= minb; t++) {
        if(checkDivide(t, maxa) && checkDivide(minb, t))
            myset.insert(t);
    }
    
    
    for(auto t = myset.begin(); t != myset.end(); t++) {
        for(int i = 0; i < a.size(); i++) {
            for(int j = 0; j < b.size(); j++) {
                if((!checkDivide(*t, a[i]) && checkDivide(b[j],*t)) ||
                   (checkDivide(*t, a[i]) && !checkDivide(b[j],*t)) || 
                   (!checkDivide(*t, a[i]) && !checkDivide(b[j],*t)))
                    toremove.insert(*t);
            }
        }
    }
    
    for(auto i : toremove) {
        auto it = myset.find(i);
        if(it != myset.end())
            myset.erase(i);
    }
    
    cout << myset.size();
    
    return 0;
}
Java Solution of Two Sets Hackerrank problem
import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
 static boolean flag=true;
 static boolean visited[]=new boolean[1000001];
 static int time[]=new int[1000001];
 static ArrayList<Integer> left=new ArrayList<Integer>();
 static ArrayList<Integer> right=new ArrayList<Integer>();
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter pw = new PrintWriter(System.out);
int n=in.nextInt();
int m=in.nextInt();
int a[]=in.nextIntArray(n);
int b[]=in.nextIntArray(m);
int ans=0;
for(int i=1;i<=100;i++)
{
	HashSet<Integer> set=new HashSet<Integer>();
	for(int j=1;j<=i;j++)
		if(j%i==0)
			set.add(j);
	boolean bool=true;
	for(int j=0;j<n;j++)
	{
		if(i%a[j]!=0)
			bool=false;
	}
	boolean bool1=true;
	for(int j=0;j<m;j++)
	{
		if(b[j]%i!=0)
			bool1=false;
	}
	if(bool&&bool1)
		ans++;
}
System.out.println(ans);
	}
	public static void DFS(int x,boolean visited[],ArrayList<Integer>[] adj)
	{
		visited[x]=true;
		for(int j=0;j<adj[x].size();j++)
		{
			if(!visited[adj[x].get(j)])
				DFS(adj[x].get(j),visited,adj);
		}
	}
	public static long pow(long n,long p,long m)
	{
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	}
	public static int BinarySearch(int val,int a[])
	{
		int low=0;
		int high=a.length-1;
		while(low<high)
		{
			int mid=(low+high)/2;
			if(a[mid]>val)
				high=mid;
			else
				low=mid+1;
		}
		return a[high];
	}
	 
 
	static class Pair implements Comparable<Pair>{
		int r;
		int v;
		Pair(int mr,int er){
			r=mr;v=er;
		}
		@Override
		public int compareTo(Pair o) {
			if(o.r>this.r)
				return -1;
			else if(o.r<this.r)
				return 1;
			else
			{
				if(o.v>this.v)
					return -1;
				else
					return 1;
			}
			}
	}
	static class TVF implements Comparable<TVF>{
		int index,size;
		TVF(int i,int c){
			index=i;
			size=c;
		}
		@Override
		public int compareTo(TVF o) {
			if(o.size>this.size)
				return -1;
			else if(o.size<this.size)
				return 1;
			else return 0;
		}
	}
	public static long gcd(long a, long b) {
		  if (b == 0) return a;
		  return gcd(b, a%b);
		}
	static class InputReader {
 
		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public   int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}
Two Sets Hackerrank problem solution in Python
aa,bb=0,0
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
b=map(int,raw_input().split())
ct=0
for i in xrange(max(a),min(b)+1):
    for j in a:
        if i%j!=0:
            break
    else:
        for k in b:
            if k%i!=0:
                break
        else:
            ct+=1
print ct

you can learn more hackerrank questions and solution Here….

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin@coderinme.com

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

2 comments: On Between Two Sets Hackerrank problem solution

Leave a reply:

Your email address will not be published.