# 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 {
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)
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;
{
}
}
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);
}

private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar, snumChars;
private SpaceCharFilter filter;

this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
} 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;
}

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``````

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

### hasectic

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

### 3 comments: On Between Two Sets Hackerrank problem solution

• Solution in Java Script:
Between Two Sets
‘use strict’;

const fs = require(‘fs’);

process.stdin.resume();
process.stdin.setEncoding(‘utf-8’);

let inputString = ”;
let currentLine = 0;

process.stdin.on(‘data’, function(inputStdin) {
inputString += inputStdin;
});

process.stdin.on(‘end’, function() {
inputString = inputString.split(‘\n’);

main();
});

return inputString[currentLine++];
}

/*
* Complete the ‘getTotalX’ function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER_ARRAY a
* 2. INTEGER_ARRAY b
*/

function getTotalX(a, b)
{
a=a.sort();
b=b.sort();

var res=0;
var x=a[a.length-1];
var y= (a.length<=b.length)? b.length : a.length;
for(let i=x;i<=b[0];i++)
{
var count1=0;
var count2=0;
for(let j=0;j<a.length;j++)
{
if(i%a[j]==0)
{
count1 = (count1+1);
}
}
for(let j=0;j parseInt(arrTemp, 10));

const brr = readLine().replace(/\s+\$/g, ”).split(‘ ‘).map(brrTemp => parseInt(brrTemp, 10));

const total = getTotalX(arr, brr);

ws.write(total + ‘\n’);

ws.end();
}

• Satyam Singnal

I was panicking and looking around for an explanation . Your post calmed me down with three lines .

• Thanks satyam