# Between Two Sets

# Between Two Sets

t_tahasin + 62 comments O(n log(n)) solution.

1. find the LCM of all the integers of array**A**.

2. find the GCD of all the integers of array**B**.

3. Count the number of multiples of LCM that evenly divides the GCD.Bmukhtar + 23 comments like this one:

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(); } int f = lcm(a); int l = gcd(b); int count = 0; for(int i = f, j =2; i<=l; i=f*j,j++){ if(l%i==0){ count++;} } System.out.println(count); } private static int gcd(int a, int b) { while (b > 0) { int temp = b; b = a % b; // % is remainder a = temp; } return a; } private static int gcd(int[] input) { int result = input[0]; for (int i = 1; i < input.length; i++) { result = gcd(result, input[i]); } return result; } private static int lcm(int a, int b) { return a * (b / gcd(a, b)); } private static int lcm(int[] input) { int result = input[0]; for (int i = 1; i < input.length; i++) { result = lcm(result, input[i]); } return result; }

dunck + 0 comments [deleted]samikshakumari27 + 0 comments why did you multiply 2 with the i in the loop ?

askarovdaulet + 6 comments why not

for (int i=f;i<=l;i+=f)

instead of

for(int i = f, j =2; i<=l; i=f*j,j++)

? Otherwise a very nice solution :)

moelldav + 3 comments "Count the number of multiples of LCM that evenly divides the GCD." is the same as "Cound the divisors of (GCD/LCM)" This will make the loop much easier.

Also notice that if (GCD/LCM) is not in integer, the result is 0.

ryanlue + 1 comment How exactly is one different from the other?

My approach was as follows:

- Divide GCD by LCM.
- Prime factorize the quotient.
- Count all unique combinations of (1..
*n*) prime factors, where*n*is the total number of prime factors. - Add 1 for the base case (LCM * 1).

ramzes_93 + 0 comments what do you mean by GCD/LCM ? can explain pleas ?

ranjan_shubham31 + 0 comments your modification to the above said approach will give wrong answer. as all mulitples of lcm will not evenly divide the gcd. so you will have to check each multiple individually.

ramzes_93 + 3 comments what do you mean by GCD/LCM ? can explain pleas ?

amitkumar9798411 + 1 comment least common multiple : LCM GCD is same as HCF : highest common factor , greatest common divisor

ramzes_93 + 0 comments thank you, bro!

axexsingh + 0 comments gcd means greatest common division and lcm means lowest common multiple

Aswaniaman28 + 0 comments divide gcd by lcm .

alex_pn + 2 comments Another suggestion to reduce the number of loop iterations

for (int i=f;i*i<l;i+=f)

then double the count and add 1 if i*i==l

abhiroyg + 1 comment For the problem's testcase (f=4, l=16), won't your loop give count as 1 ?

77shashi_mishra + 0 comments it will never go inside for if i*i< l for case of (f=4, l=16)

anashukla17 + 0 comments why is it i*i?

m4manishpushkar + 0 comments because the value of i will be getting doubled for getting next factor easily.

chandramnataraj1 + 0 comments i can only be multiples of lcm(a), that is why j starts at 2 and increases

ayusofayush + 0 comments [deleted]lemanisar23 + 0 comments thank you so much for your advise askarovdaulet

[deleted] + 0 comments [deleted]__grj + 0 comments [deleted]KeyurPotdar + 0 comments [deleted]azicon + 2 comments 100*99*97*91*89*83*79*73*71*67~1.7*1e19, so if b = {100, 99, 97, 91, 89, 83, 79, 73, 71, 67} lcm(b) be over integer range

ishita_ghosh + 2 comments for this case, why is lcm coming negative?

azicon + 1 comment because lcm(b)~1.77*10^19, which is out of integer range, even long long range. So integer overflow happens (https://en.wikipedia.org/wiki/Integer_overflow) // integer range is from -2^31 to 2^31-1~2.15*10^9, long long range is from -2^61 to 2^61-1~3.21*10^18.

ishita_ghosh + 1 comment Yes i have understood. But how can we proceed with program when our lcm is coming to be negative. Shouldnt the program logic give wrong results then?

azicon + 2 comments I've noticed hackerRank has poor tests. That is why such solutions pass tests. Specifically in this task variable l can not be greater than 100. So I recommend you return 101, when result variable from lcm fuction is coming greater than 100. It will prevent for loop which count "count" variable So sorry for my poor english, it is not my native language

ishita_ghosh + 1 comment ty

azicon + 0 comments you are welcome

bitralahari20171 + 0 comments yeah i too feel that hkrnk has poor tstcases

alaniane + 0 comments When you overflow an integer, it will wrap around. At the assembly level you can check to see the zero and overflow flags have been set. So an overflow on a signed int can set the bit that indicates that the number is negative.

ikeka95 + 0 comments It should not go out of range. Use { function lcm(arr){ var multiples = {}, factors, f = [], lcm = 1;

`for(var i of arr){ factors = primes(i); f = []; for(var factor of factors){ if(f.indexOf(factor) == -1){ f.push(factor); if(typeof multiples[factor] == 'undefined'){ multiples[factor] = countElement(factors, factor); }else{ multiples[factor] = Math.max(multiples[factor], countElement(factors, factor)); } } } } for(var i in multiples){ lcm *= i ** multiples[i] ; } return lcm;`

}

function primes(number) { number = Math.abs(number); var divider = 2, dividend, factors = [];

`while(number != 1){ dividend = number/divider; if (dividend.toString().indexOf('.') != -1) { divider++ continue; } number = dividend; factors.push(divider); } return factors;`

}

function countElement(haystack, needle) { var count = 0; for(var i of haystack){ if(JSON.stringify(i) == JSON.stringify(needle)) count++; } return count; } }

ishita_ghosh + 0 comments [deleted]sumit371996 + 2 comments copy paste maar dia bhai

rajat_yadav + 1 comment aur kya kar sakta hai tu apni university ka naam hi dubaayega kuch seekh le in iit main padne walon se jo 50-50 lakh ka package kaise le jaate hain copy paste maarkar nahin kabhi hackerrank par unki profile check karna pata cjal jaayega

vivek4296 + 0 comments sahi bola, tera jaisa kahan hi h...yahan koi only u will get 50 lakh i know!!

rajat_yadav + 6 comments ye le solution samajh maine khudne banaya hai 2 ghante baith kar tu bhi bana saktaa hai agar hai himmat

static int getTotalX(int[] a, int[] b) { int x=1,r=0,j=0,count=0; int[] d = new int[101]; for(x=1;x<101;x++){ int c=0; for(int i=0;i<a.length;i++) { if(x%a[i]==0&&x>=a[i]){ c++; } } if(c==a.length){ d[j]=x; r++; j++; } } for(j=0;j<r;j++){ int c=0; for(int i=0;i<b.length;i++){ if(b[i]%d[j]==0){ c++; } } if(c==b.length){ count++; } } return count; }

shubhamchaudha11 + 0 comments Hi Rajat, can you please tell me about significance of "j"?

vivek4296 + 0 comments [deleted]vivek4296 + 0 comments [deleted]vivek4296 + 0 comments @rajat_yadav ye le.. tere wale se thoda easy hai

`static int gcd(int l,int e) { if(e==0) { return l; } else { return gcd(e,l%e); } } static int lcm(int[] e) { int ans=1; for(int i:e) { ans=(ans*i)/gcd(ans,i); } return ans; } static int getTotalX(int[] a, int[] b) { /* * Write your code here. */ int count=0; int g=b[0]; int l=lcm(a); for(int i=1;i<b.length;i++) { g=gcd(g,b[i]); } int m=l; int i=1; while(m<=g) { m=l*i; if(g%m==0) { count++; } i++; } return count; }`

dsgarg71 + 0 comments ugly code

Ashutosh_Awasthi + 1 comment public static int getTotalX(List a, List b) {

`int counter = 0; if (a.Count>=1 && a.Count <= 10 && b.Count>=1 && b.Count <= 10) { int max1 = a.Max(x => x); int max2 = b.Max(x => x); int min1 = a.Min(x => x); int min2 = b.Min(x => x); int MaxCondition = max1 > max2 ? max1 : max2; int minCondition = min1 > min2 ? min2 : min1; for (int i = minCondition; i <=MaxCondition && i<=100; i++) { if (a.All(x => i % x == 0) && b.All(y => y % i == 0)) { counter++; } } } return counter; }`

sk4641230 + 3 comments hi, your code is really nice and optimized. Can you check my code. It passed all testcases but i want to know is it possible to optimize it?

`def getTotalX(a, b):`

`x=a[len(a)-1] y=b[0] count=0 for p in range(x,y+1): chk=0 for i in b: if i%p!=0: chk=1 break chk1=0 for i in a: if p%i!=0: chk1=1 break if chk==0 and chk1==0: count+=1 return count`

iampetermitsel + 1 comment Hi, I had a similar approach at first and optimized this way

results=[] for i in range(1,max(b)+1): if all(i%anum==0 for anum in a) and all(bnum%i==0 for bnum in b): results.append(i) return (len(results))

MADMAN007 + 2 comments Hi there. A nice solution for the beginners. But instead of using max(b)+1 in the loop range, it is sufficient to use min(b)+1.

csimpilimpihova1 + 0 comments ...and for start max(a), and for step max(a)

csimpilimpihova1 + 1 comment By the way my first attempt timed out on two test cases (whereas iampetermitsel's solution works). Can somebody help me, how is my solution different from his?

`min_b = b[0] max_a = a[-1] common_multiples_a = [] elem = max_a while elem <= min_b: if all(elem % item == 0 for item in a): common_multiples_a.append(elem) elem += max_a count = 0 for elem in common_multiples_a: if all(item % elem == 0 for item in b): count +=1 return count`

justsuyash + 0 comments His is Java Code whereas yours is a python code. It will takes longer to Execute. So sometime that happens.

baruneshgambler + 0 comments Its a little optimized version of your code

def getTotalX(a, b):

`x=a[len(a)-1] y=b[0] count=0 for p in range(x,y+1): chk=0 for i in b: if i%p!=0: chk=1 break if chk == 1: continue else: chk1=0 for i in a: if p%i!=0: chk1=1 break if chk1==0: count+=1 return count`

twishabansal + 0 comments You can continue for chk1 only if chk==0, otherwise no need

adityashaw2 + 1 comment This is a very lengthy approach to the problem.

rajat_yadav + 5 comments small

static int getTotalX(int[] a, int[] b) { int x=1,r=0,j=0,count=0; int[] d = new int[101]; for(x=1;x<101;x++){ int c=0; for(int i=0;i<a.length;i++) { if(x%a[i]==0&&x>=a[i]){ c++; } } if(c==a.length){ d[j]=x; r++; j++; } } for(j=0;j<r;j++){ int c=0; for(int i=0;i<b.length;i++){ if(b[i]%d[j]==0){ c++; } } if(c==b.length){ count++; } } return count; }

NSterling + 1 comment Could you explain what exactly is going on with this?

VijiSekar + 0 comments There, all the multiples common to first array(a) elements is found upto 100 and stored in 'd'. and then the elements that are in second array(b) that becomes the multiples of any of the elements is found and count is incremented accordingly

snkt_pat2 + 7 comments Small

def getTotalX(a, b): nmax,nmin,count = max(a),min(b),0 for i in range(1,int(nmin/nmax)+1): if(sum((i*nmax)%n for n in a)+sum(n%(i*nmax) for n in b))==0: count+=1 return count

vaishnavipariti + 1 comment i am not getting the logic can you please explain?

parikshitsharma2 + 0 comments It's pretty easy

range(1,int(nmin/nmax)+1) -

Loops through the possibilites between nmax and nmin

sum((inmax)%n for n in a) == 0

Finds whether chosen n is multiple of nmax by using modulus function

sum(n%(inmax) for n in b) == 0

Finds whether chosen n is a factor of bmin

I hope you got it..

gkjha009 + 7 comments We need to find numbers b/w two arrays, we can take max from a and min from b, then we can do calculation to find numbers.

This is what i'm doing in m beloved JS.

function getTotalX(a, b) { let total = 0; let maxA = Math.max(...a); let minB = Math.min(...b); let number = maxA;

`let allElementsAreMultiple = false; let numberIsMultipleOfAll = false; while(number <= minB){ console.log('aMax ', maxA,'bMin ', minB, 'number ', number); // Every element of array must be a multiple of considerd number allElementsAreMultiple = a.every(ele => number%ele === 0 ); numberIsMultipleOfAll = b.every(ele => ele%number === 0 ); if( allElementsAreMultiple && numberIsMultipleOfAll ) total++; number++; } return total;`

}

That makes it very easy for me.

aheza007 + 0 comments i think u shouldn't compute

**numberIsMultipleOfAll**if**allElementsAreMultiple**is**false**boertjie_seun + 0 comments This is a great solution. I implemented it in Swift

func getTotalX(a: [Int], b: [Int]) -> Int { var allElementsAreMultiple = false var numberIsMultipleOfAll = false let minB = b.reduce(b[0], min) var total = 0 for i in 1...minB { allElementsAreMultiple = a.map { return i % $0 == 0 }.reduce(true, {$0 && $1}) numberIsMultipleOfAll = b.map { return $0 % i == 0 }.reduce(true, {$0 && $1}) if (allElementsAreMultiple && numberIsMultipleOfAll) { total += 1 } } return total }

renatofrancisco + 0 comments Nice logic!

renatofrancisco + 1 comment The same logic in C#:

`public static int getTotalX(List<int> a, List<int> b) { int total = 0; int number = a.Max(); Enumerable.Range(number, b.Min()) .ToList() .ForEach(n => { if (a.All(e => number % e == 0 || e % number == 0) && b.All(e => number % e == 0 || e %number == 0)) total++; number++; }); return total; }`

heiks + 5 comments Hello!

I noticed that Your answer goes through way too many iterations and doesn't take large enough steps, there can be no correct answer between a.Max() and 2a.Max(), therefore skipping those is a good idea.

Looping through by generating an amount of integers also isnt really necessary, just start from lowest possible correct answer ( a.Max() ) and make sure youre not over the largest possible ( b.Min() ) correct answer.

Works like a charm :).

Here is the resulting code with comments.

`public static int getTotalX(List<int> a, List<int> b) { /*Starting from 0 found, storing largest value in A and smallest value in b. Setting starting point to largest value in A.*/ int foundCount = 0, maxA = a.Max(), minB = b.Min(), current = maxA; while (current <= minB) { /*If the current value is divisible by all members of both arrays, then it's the one we want.*/ if (a.All(e => current % e == 0 || e % current == 0) && b.All(e => current % e == 0 || e % current == 0)) foundCount++; /*Iterate the value by largest member of divisors, no reason to take smaller steps.*/ current+= maxA; }; return foundCount; }`

" C# " for everyone CTRL+F-ing.

//Stored a.Max() and b.Min() as dsgarg71 suggested below :).

renatofrancisco + 1 comment Very nice optimization! I really was not realized it. Thanks. :)

heiks + 0 comments Thanks :). dsarg71 found another neat optimization. I've added that as well.

ikeka95 + 0 comments Wow It did the magic. Thanks

dharrison2010 + 3 comments How in the world did you know to use this to find the answer?

I would really like to know.

What did you study to know this? Nothing I have ever covered in C# would tell me to use something like this to come up with this answer, hell I couldn't even understand the frickin problem. I just don't get how peeps look at something and boom know what to apply and where...really discourages me.

rock_sunilkumar1 + 0 comments its all about mathematics people will learn eventually

heiks + 0 comments Hey

Dont get discouraged :). I think studying something specifically, to solve these types of problems, would be a waste of time. These types of problems are really about building something from LEGO-s. The LEGO-s being things you know about any programming language, or problem solving overall. You just put pieces together and see what fits. If you wanted to improve yourself, just get more LEGO-s, learn more about the language, its possibilities etc...

With these types of problems, theres always a distict correct answer, which gives you a solid metric, as to how right you are. If youre wrong, you get the wrong result, so its really easy to get feedback and improve.

If understanding the problem overall was the difficult part, then maybe try some simpler problems first, this specific problem can be solved in about infinite ways, some faster/optimal, some not.

Keep trying ;), you'll get it eventually.

nightrush1256 + 0 comments I had the same problem with those peoples who have been into this and making sure that you get the correct anwser for sure with proofreading services UK where peoples were selected to do some unique task. also people should have known that its not quite well or working.

rogue93 + 0 comments Java version of this code if anyone wants it. PS: Very simple and elegent logic btw pal. Thank you :) !

`public static int getTotalX(List<Integer> a, List<Integer> b) { Collections.sort(a); Collections.sort(b); int maxA = a.get(a.size()-1); int minB = b.get(0); int totalX = 0; int currentVal = maxA; while(currentVal <= minB) { final int current = currentVal; if(a.stream().allMatch(e->current % e == 0 || e % current == 0) && b.stream().allMatch(e->current % e == 0 || e % current == 0)) { totalX++; } currentVal += maxA; } return totalX; }`

kimketchum15 + 0 comments [deleted]kimketchum15 + 0 comments simplified

function getTotalX(a, b) { // Write your code here let total = 0; let current = a[a.length - 1]; while(current <= b[0]){ if( a.every(n => !(current%n)) ) { if( b.every(n => !(n%current)) ) { total++; } } current++; } return total; }

andy89 + 0 comments [deleted]joshumcode + 1 comment This is a fucking work of art.

snkt_pat2 + 0 comments Thanks a lot

max_aka21 + 1 comment why "i x nmax"?

snkt_pat2 + 0 comments Because we do not need to iterate through all the numbers between nmax and nmain

We need to iterate through just the 'multiples of nmax' between the range of nmax to nmin. Because non-multiples of nmax are however not going to satisfy the conditions provided.

Hope, it helps you.

pathansuhana969 + 1 comment can u explain the for loop range??

snkt_pat2 + 0 comments I am just iterating through the

**multiples nmax**within the range of**nmax to nmin**because the**non multiples nmax**are however not gonna satisfy the conditions provided so we can just skip these numbers increasing speed of the overall execution.**range(1,int(nmin/nmax)+1)**The range gives the count of

**multiples of nmax**present within the range of**nmax and nmin**e.g

nmax=4

nmin=12

So, range(1,int(nmin/nmax)+1) = range(1,4) = [1,2,3]

There are 3

**multiples of 3**within the**range of 3 to 6**Hope this helps.

evan51 + 2 comments Real programmers can program fortran in any language. Go back to CS101 and learn to use variable names that have meaning. a,b,x,r,j,d,c provide no context. This code would be unacceptable in a commericial application.

dsgarg71 + 1 comment whenever I see variables like a,b,x,r,i,k etc, I get a near heart attack.

sivashankar623 + 0 comments RIP

Braunz + 0 comments its not for commerical use...its for practice.. calm down... a big part of the site are the competitions. it's waste of time to come up with detailed names for every varaible in every problem while the timer is ticking down

vivek4296 + 0 comments static int gcd(int l,int e) { if(e==0) { return l; } else { return gcd(e,l%e); } } static int lcm(int[] e) {

int ans=1; for(int i:e) { ans=(ans*i)/gcd(ans,i); } return ans; } static int getTotalX(int[] a, int[] b) { /* * Write your code here. */`int count=0; int g=b[0]; int l=lcm(a); for(int i=1;i<b.length;i++) { g=gcd(g,b[i]); } int m=l; int i=1; while(m<=g) { m=l*i; if(g%m==0) { count++; } i++; } return count; }`

deboshreedas27f1 + 0 comments what is 101 here

MAYUR_2 + 0 comments in my code time complexity is quite less:

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`static int getTotalX(int[] a, int[] b) { int i,j,k; Vector <Integer> v1 = new Vector <Integer> (); for(i=1;i<=b[(b.length-1)];i++) { int c=0; for(j=0;j<b.length;j++) { if(b[j]%i==0) { c++; } } if(c==b.length) { v1.add(i); } } int c1; int c2=0; for(k=0;k<v1.size();k++) { c1=0; int a1= v1.get(k); for(i=0;i<a.length;i++) { if(a1%a[i]==0) { c1++; } } if(c1==a.length) { c2++; } } return c2; // Complete this function } 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(); } int total = getTotalX(a, b); System.out.println(total); in.close(); }`

}

v_borisok + 1 comment Redundant memory allocation. There is no need to use arrays.

rishabh0_9 + 0 comments Here i wrote the code without using any array or vector

int total = 0; if(a[(a.length-1)]<b[0]){ for(int i=a[(a.length-1)]; i<b[0]+1; i++){ int c=0; for(int j=0; j<b.length; j++){ if(b[j]%i==0) c++; } if(c==b.length){ int c1=0; for(int k=0; k<a.length; k++){ if(i%a[k]==0) c1++; } if(c1==a.length){ total++; } } } } else{ for(int i=b[0]; i<a[(a.length-1)]+1; i++){ int c=0; for(int j=0; j<b.length; j++){ if(b[j]%i==0) c++; } if(c==b.length){ int c1=0; for(int k=0; k<a.length; k++){ if(i%a[k]==0) c1++; } if(c1==a.length){ total++; } } } } return total;

tecnocratay + 0 comments i didnt get why j=2 in this line bellow

for (int i = f, j = 2; i <= l; i = f * j, j++) {

could someone clarify me?

vishalo_ojha + 0 comments I am a beginner. So can anyone tell me if this is more efficient than the above code or not?

....... ....... for (int i = 0; imaxA){ maxA=a[i]; }

`public static int lcm(int[] ai){ int lcm1= maxA; int lcmMin=lcm1; while(true){ for (int i =0; i<ai.length;i++){ if(lcm1%ai[i]==0){ countA++; } } if (countA==ai.length){ lcmMin=lcm1; break; } else{ lcm1++; } } return lcmMin; }`

nilomishah63 + 0 comments [deleted]__PinkMan + 1 comment How does this for loop works?

for(int i = f, j =2; i<=l; i=f*j,j++)

bitralahari20171 + 0 comments u have posed the doubt bit a time ago. hope my clarification might help u

f is lcm of a, l is gcd of b.i is initialised to f and j is initialised to 2, the termination condition is that i must not exceed l .inside the loop,we need to check if either i or its multiples divide l and their count.to get the next multiple of i,we use j.after the 1st iteration ,i is assigned the value of its next multiple by multiplying its current value with j and j is incremented and the loop goes on

whoamii + 0 comments I have the same solution but i don't want the complexity is O(nlogn). can explain?

PedroStu + 0 comments Another approach to this problem is using C++ and vectors Also, I think simply using factors instead of finding GCD and LCM can be a more simpler as well as transparent way:

`#include <iostream> #include <vector> #include <algorithm>`

`using namespace std; void factorsOf(int number, vector<int> &arr) { int temp, i=0; for(temp=1;temp <= number;temp++) { if ((number % temp) == 0 ) { arr.push_back(temp); i++; } } } int getTotalX(vector<int> &a, vector<int> &b) { vector<int> allFactors; //THIS VECTOR COLLECTS ALL THE FACTORS OF THE ELEMENTS OF BOTH THE ARRAYS. vector <int> temp; int size_a = a.size(); int size_b = b.size(); int count=0,i=0,j=0,flag1,flag2; //COLLECTING ALL THE FACTORS OF ALL THE ELEMENTS OF BOTH THE ARRAYS, SO AS TO LIMIT THE ITERATIONS NEEDED FOR SOLVING THE PROBLEM while(size_a != 0) //RUNNING THROUGH THE ENTIRE ARRAY { factorsOf(a[size_a-1], temp); //NOW, TEMP HAS STORED THE FACOTRS OF THE NUMBER SENT TO THE FUNCTION allFactors.insert(allFactors.end(), temp.begin(), temp.end()); size_a--; } //REPEATING THE SAME PROCESS FOR ARRAY B while(size_b != 0) { ////cout<< endl<< size_b-1 << ", Value: "<< b[size_b-1]; factorsOf(b[size_b-1], temp); //NOW, TEMP HAS STORED THE FACOTRS OF THE NUMBER SENT TO THE FUNCTION allFactors.insert(allFactors.end(), temp.begin(), temp.end()); size_b--; } //NOW SORTING, REMOVING DUPLICATES AND FINALLY RESIZING THE VECTOR sort(allFactors.begin(), allFactors.end()); allFactors.erase(unique(allFactors.begin(), allFactors.end()), allFactors.end() ); for(int j=0;j<allFactors.size();j++) { flag1 = 1; for(i=0;i<a.size();i++) { if(allFactors[j] % a[i] != 0) { flag1 = 0; break; } } if(flag1 == 1) { flag2 = 1; for(i=0;i<b.size();i++) { if(b[i] % allFactors[j] != 0) { flag2 = 0; break; } } if(flag2 == 1) { count++; cout<< endl<<"RESULT: "<< allFactors[j]; } } } return count;`

}

`int main() { vector <int> a = {2, 4}; vector <int> b = {16, 32, 96}; int total = getTotalX(a, b); cout <<endl<<"THE TOTAL IS: " <<total << "\n"; }`

elderaramka + 0 comments Same solution using Java8:

`static int getTotalX(List<Integer> a, List<Integer> b) { int result = 0; int gcd = getValue(b, gcd()); int lcm = getValue(a, lcm()); for (int i = lcm; i <= gcd; i += lcm) { if (gcd % i == 0) { result++; } } return result; } private static int getValue(List<Integer> numbers, BiFunction<Integer, Integer, Integer> function) { int result = numbers.get(0); for (int i = 1; i < numbers.size(); i++) { result = function.apply(result, numbers.get(i)); } return result; } private static BiFunction<Integer, Integer, Integer> lcm() { return (a, b) -> a * (b / gcd().apply(a, b)); } private static BiFunction<Integer, Integer, Integer> gcd() { return (a, b) -> { while (b > 0) { int temp = b; b = a % b; a = temp; } return a; }; }`

ismailkuet + 1 comment Python 3 ::

import math from functools import reduce def gcd_of_list(list): x = reduce(math.gcd, list) return x def lcm(denominators): return reduce(lambda a, b: a * b // math.gcd(a, b), denominators) l = lcm(a) g = gcd_of_list(b) i = lcm(a) ans = 0 while i <= g: if g%i == 0: ans += 1 i += l return ans

shadymademeyrs + 0 comments These one liner python codes are really amazing. Nice code :)

lakshmi_koppara1 + 0 comments Awesome.. So clear and simple

pujitha_gaddale + 1 comment its wrong

zaramaths123 + 0 comments why is it wrong?

007ravinash + 0 comments for(int i = f, j =2; i<=l; i=f*j,j++)

can anyone explain this loop?

NicolasBi + 10 comments Thank you for your solution, you helped me produce this oversized Python 3 code :

#!/bin/python3 import sys from functools import reduce def lcm(a: int, b: int) -> int: return a * b // gcd(a, b) def lcm_list(lst: list) -> int: return reduce(lcm, lst) def gcd(a: int, b: int) -> int: while a % b != 0: a, b = b, (a % b) return b def gcd_list(lst: list) -> int: return reduce(gcd, lst) def evenly_divides(number: int, divisor: int) -> bool: return (number % divisor) == 0 def get_input(): n, m = input().strip().split() n, m = [int(n), int(m)] a = [int(a_temp) for a_temp in input().strip().split()] b = [int(b_temp) for b_temp in input().strip().split()] return n, m, a, b def main(): n, m, a, b = get_input() # Find LCM of all integers of a lcm_value = lcm_list(a) # Find GCD of all integers of b gcd_value = gcd_list(b) # Count the number of multiples of LCM that evenly divides the GCD. counter = 0 multiple_of_lcm = lcm_value while multiple_of_lcm <= gcd_value: if evenly_divides(gcd_value, multiple_of_lcm): counter += 1 multiple_of_lcm += lcm_value print(counter) if __name__ == "__main__": main()

stregz + 1 comment perhaps easier to understand, but your organization is on point. Uses built-in gcd:

#!/bin/python import sys from fractions import gcd n,m = raw_input().strip().split(' ') n,m = [int(n),int(m)] A = map(int,raw_input().strip().split(' ')) B = map(int,raw_input().strip().split(' ')) def LCM(a, b): return (a*b)//gcd(a,b) lcm = reduce(LCM, A, 1) gcd = reduce(gcd, B) lcm_copy = lcm count = 0 while lcm <= gcd: if(gcd % lcm) == 0: count += 1 lcm = lcm + lcm_copy print(count)

askarovdaulet + 5 comments Hmm, it seems the initializer in reduce(LCM,A,1) is not needed, since the behavior of

`reduce`

for single-element lists is just returning the element. For the sake of curiosity, here's a more packed version of your approach. Arguably, it does push the limits of readability :)import sys from functools import reduce from fractions import gcd input() a = map(int,input().strip().split()) b = map(int,input().strip().split()) lcm_a = reduce(lambda x,y: x*y//gcd(x,y), a) gcd_b = reduce(gcd, b) print(sum(1 for x in range(lcm_a,gcd_b+1,lcm_a) if gcd_b%x==0))

amelnychukoseen + 0 comments Damn this is nice.

mushthofa + 0 comments Nice

kanabos + 1 comment Not a big change but you can iterate less times:

import sys from functools import reduce from fractions import gcd input() a = map(int,input().strip().split()) b = map(int,input().strip().split()) lcm_a = reduce(lambda x,y: x*y//gcd(x,y), a) gcd_b = reduce(gcd, b) gcd_b_copy = gcd_b print(sum(1 for x in range(lcm_a,gcd_b+gcd_b_copy,lcm_a) if gcd_b%x==0))

it_beast + 0 comments Awesome

ssbreckenridge + 0 comments Note for python3.7:

`DeprecationWarning: fractions.gcd() is deprecated. Use math.gcd() instead.`

P1zzAdr0hn3 + 2 comments #!/bin/python3 import sys n,m = input().strip().split(' ') n,m = [int(n),int(m)] a = [int(a_temp) for a_temp in input().strip().split(' ')] b = [int(b_temp) for b_temp in input().strip().split(' ')] a.sort() b.sort() ausgabe = 0 for q in range(b[0] +1): if q >= a[-1]: for t in range(n): if q % a[t] != 0: break if t == n -1: for g in range(m): if b[g] % q != 0: break if g == m -1: ausgabe += 1 print(ausgabe)

AffineStructure + 2 comments 3 for loops = O(n^3)

P1zzAdr0hn3 + 6 comments Yeah thats not nice... Your approach using lists and all() is much more elegant.

#!/bin/python3 import sys n,m = map(int, input().strip().split(' ')) a = list(map(int, input().split())) b = list(map(int, input().split())) ausgabe = 0 for q in range(max(a), min(b) +1): if all(q % arr == 0 for arr in a) and all(brr % q == 0 for brr in b): ausgabe += 1 print(ausgabe)

namanrocks94 + 1 comment amazing way, but would this be O^2 ??

P1zzAdr0hn3 + 1 comment i think its O(2n^2)

SalmanBhai + 1 comment O(2n^2) is supposed to be O(n^2). Constants aren't taken into account.

P1zzAdr0hn3 + 1 comment Asymptomatic complexity... i think now i got it :D

paul_schmeida + 1 comment It's asymptotic actually :)

P1zzAdr0hn3 + 0 comments :D I knew it was something like that.

suryach750 + 0 comments can you test this i/p: 3 2 4 8 12 12 24

MatricksDecoder + 1 comment print(len([num for num in range(max(a),max(b)+1) if (all(num%i==0 for i in a)) and all(i%num==0 for i in b)]))

zad23 + 0 comments surely should be min(b)+1 not max(b)+1

ash_jo4444 + 0 comments Awesome solution !!

washimdas2013 + 0 comments Superb Dude!!

Rishi_Kumar_Soni + 0 comments can yo tell me the use of

**all**

isabella_xy_sun + 2 comments Hi there. I'm a beginner in Python. I don't know too much about complexity. Below is my solution in Python 2. Is my way efficient? Thank you!

#!/bin/python import sys n,m = map(int,raw_input().strip().split(' ')) a = map(int,raw_input().strip().split(' ')) b = map(int,raw_input().strip().split(' ')) final = 0 lower,upper = max(a),min(b) for i in xrange(lower,upper+1): if sum(1 for k in a if i%k == 0) == n and sum(1 for k in b if k%i == 0) == m: final += 1 print final

AffineStructure + 1 comment Your solution is a bruteforce solution that checks each of the digits between the sets, therefore it is not efficient. The editorial shows a clever solution in O(sqrt(n)) solution.

For the runtime of your code, you have two generator comprehensions, where each comprehension checks through each element inthe length of the list for every i in the range.

If we were to compute what the runtime, it should be [(upper-lower) * (len(a) + len(b))] = O(n^2) #someone correct me if this is wrong

P1zzAdr0hn3 + 1 comment for, for would be O(n^2) but we have for, for and for O(2n^2)

AffineStructure + 1 comment With time complexity we drop out the constant term.

https://en.wikipedia.org/wiki/Time_complexity

"For example, if the time required by an algorithm on all inputs of size n is at most 5n^3 + 3n for any n (bigger than some n_0), the asymptotic time complexity is O(n^3)."

P1zzAdr0hn3 + 0 comments ... you're right^^

chinmay_zare + 0 comments its most lucid and probably the best algorithm ! Thanks. it made me understand the concept.

skdubey + 0 comments your program has one error... it is not compile

__grj + 0 comments [deleted]SebastianNielsen + 1 comment What is this syntax?

def gcd(a: int, b: int) -> int:

I have never seen that before in python3, couldyou ellaborate on what it is for? At first i thought that gcd only accepted a and b to be an integer. But when I tried setting a to an float, no error accured.

- What is it for?

aymanabuelela + 0 comments Function annotations https://www.python.org/dev/peps/pep-3107/

[deleted] + 5 comments Here is smaller code bro,

def getTotalX(a, b): total = 0 for x in list(range(a[-1], b[0] + 1)): hold = 0 for v in a: if (x % v == 0): hold += 1 else: hold = 0; break for c in b: if (c % x == 0): hold += 1 else: hold = 0; break if (hold == len(a) + len(b)): total += 1 return total

anurag12345 + 0 comments Awesome bro

chandrakanthshy + 0 comments add a if condition above the 3rd for loop like:

if hold > 0:

`for c in b: .... ....`

gkjha009 + 0 comments Great,

We not only need to solve this puzzle but at the same time think of time complexity :).

We need to find numbers b/w two arrays, we can take max from a and min from b, then we can do calculation to find numbers.

This is what i'm doing in m beloved JS.

function getTotalX(a, b) { let total = 0; let maxA = Math.max(...a); let minB = Math.min(...b); let number = maxA;

`let allElementsAreMultiple = false; let numberIsMultipleOfAll = false; while(number <= minB){ console.log('aMax ', maxA,'bMin ', minB, 'number ', number); // Every element of array must be a multiple of considerd number allElementsAreMultiple = a.every(ele => number%ele === 0 ); numberIsMultipleOfAll = b.every(ele => ele%number === 0 ); if( allElementsAreMultiple && numberIsMultipleOfAll ) total++; number++; } return total;`

}

That makes it very easy for me.

marcomereu2015 + 0 comments Thank you!

zaramaths123 + 0 comments i don't get why we use this line? if (hold == len(a) + len(b)):

jamesallenvinoy + 1 comment "lcm(a: int, b: int) -> int" , what is the concept in python behind this??

amitkumar10591 + 0 comments Will the solution return correct values when we use the below test case: 3 3 7 8 10 280 560 1120

I think the solution above would give incorrect results.

suryabteja + 0 comments Cool code!! my code to find number of factors def nooffactors(z): print(sum(int(z)%i == 0 for i in range(1,z+1) )) return

martin89 + 0 comments This is far far more readable than prior solutions. I like it. SImilar to mine in c#

`static int getTotalX(int[] a, int[] b) { var lcm = LCM(a); var gcf = GCF(b); var candidate = lcm; var count = 0; while (candidate<=gcf) { count += gcf % candidate ==0 ? 1 :0; candidate += lcm; } return count; } static int LCM(int []x) => x.Aggregate(lCM); static int GCF(int []x) => x.Aggregate(gCF); static int gCF(int a, int b) => b == 0 ? a : gCF(b, a % b); static int lCM(int a, int b) => (a *b) / gCF(a, b);`

nalin39 + 0 comments So thats what he meant(calculating the counter that way). Not sure, but some how I misunderstood "Integer being considered". Being a newbie here, just didn't notice this section. A lot has already been said and done, and I was going crazy over the tests. :-)

LittleHacker12 + 0 comments [deleted]LittleHacker12 + 1 comment [deleted]t_tahasin + 0 comments Your lcm and gcd functions looks fine. But the way you calculated the lcm or gcd for the whole array is not correct. In your current implementation you will get the lcm or gcd only for the last two elements of the array. Try to find how to calculate those for the whole array.

For step-3, if

**f**evenly divides**g**, then count the number of multiples of**f**which evenly divides**g**. Evenly divides means if**g**is divided by**f**then the remainder will be 0.g%f == 0

and multiple of f means f,2*f,3*f,4*f... so on. In your case you you have to count the number of multiple of

**f**which evenly divides**g**. likeg%(f*i)==0, where i=1,2,3... until i*f<=g;

loginhack + 0 comments [deleted]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; }

askarovdaulet + 1 comment Exactly what I thought as well. Nice and short in Python 3 without math.gcd:

import sys def lcm(a): if len(a)==1: return a[0] if len(a)==2: return a[0]*a[1]//gcd((a[0],a[1])) return lcm((a[0],lcm(a[1:]))) def gcd(a): if len(a)==1: return a[0] if len(a)==2: return gcd((a[1],a[0]%a[1])) if a[1]!=0 else a[0] # Euclid's alg return gcd((a[0],gcd(a[1:]))) input() lcm_a = lcm([x for x in map(int,input().strip().split())]) gcd_b = gcd([x for x in map(int,input().strip().split())]) print(sum(1 for x in range(lcm_a,gcd_b+1,lcm_a) if gcd_b%x==0))

kevinoberoy98 + 0 comments Can you please explain the code

sungmkim80 + 0 comments I wish I had come up with this algorithm. I brute forced the solution. That means test cases weren't testing if the code is optimal or not.

anmolsaxena3 + 1 comment How did you calculate O(n log(n))

t_tahasin + 3 comments actually for both of the steps 1 & 2 the complexity will be

**O(n log(b))**.Here

**n**is the length of the array and**b**is the smaller integer of a pair(a,b) for which we calculate the GCD/LCM.For simplicity we call it O(n log(n)) instead of O(n log(b)).

Explanation: To calculate the GCD or LCM for the whole array we need to run a loop up to the length of the array which is

**n**and inside that loop we need to calculate GCD/LCM which will take**log(n)**. like below.previousGCD = array[0]; for(int i = 1; i<n; i++) {// n previousGCD = GCD(previousGCD, array[i]);//log(n) }

so the complexity is O(n*log(n)). Same goes for LCM also.

anmolsaxena3 + 0 comments Thanks!

shradhaagar_09 + 0 comments I have calculated lcm of first array and gcd of second array. After that what should i do?

[deleted] + 1 comment Code for the above solution:

//Ecluids algorithm to find gcd /* gcd(m,n)

pseudo code while n (!=0) { r=m%n; m=n; n=r; } */

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class solution { int gcd(int m,int n) { if(n==0) //gcd(m,0) ==>gcd ends ==> m (is the gcd) { return m; } else { return gcd(n,m%n); } } int lcm(int[] a,int n) { int res =1,i; for (i=0;i<n;i++) { res =res*a[i]/gcd(res,a[i]); } return res; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); //finding lcm of a no using now reduction of gcd to lcm solution ob = new solution(); int n = scan.nextInt(); int m =scan.nextInt(); int[] a = new int[n]; //find lcm int[] b = new int[m]; //find only gcd for (int i=0;i<n;i++) { a[i] = scan.nextInt(); } //finding lcm of the first array int result = ob.lcm(a,n); int result2=1; for (int i=0;i<m;i++) { int r =1; b[i] = scan.nextInt(); } // Finding only the gcd of the second array int no =b[0]; for(int i=1;i<m;i++) { no=ob.gcd(no,b[i]); } //count the no of multiples of lcm that evenly divides gcd //System.out.println("Results:"+result); //System.out.println("Result2:"+no); int count = 0; //count the no of multiples int f = result; //lcm int l = no; //gcd for (int i=f;i<=l;i+=f) { if(l%i==0){ count++;} } System.out.println(count); } }

positivedeist_07 + 0 comments Elegant code with perfect comments :) I'm new to DP. Shouldn't we use memoization here to optimize the runtime? Or is this the best solution possible? Pls clear me out here!!

kenx405839 + 1 comment Thanks Below is my implementation in scala Btw, I think the third would be the number of divisors of result_1/result_2

def gcd(a: Int, b: Int):Int=if (b==0) a.abs else gcd(b, a%b) def lcm(a: Int, b: Int)=(a*b).abs/gcd(a,b) val g = a.reduceLeft((x,y) => lcm(x,y)) val l = b.reduceLeft((x,y) => gcd(x,y)) val ans = (1 to l/g) count(x => l%(x*g) == 0 ) println(ans.toInt)

AffineStructure + 1 comment Hey, where are you learning scala? Thats the language I want to learn the most right now.

kenx405839 + 0 comments Hi, I took two courses from coursera, and I read a book called "Learning Scala".

iframe + 0 comments But you have n and m ? isn't o(m log n)

praveenbdj + 1 comment In that case my friend, please explain me this. lets consider set A to be {2, 4} and set B to be {20, 40} then LCM of set A is 4 and GCD of set B is 20. Now according to point 3 of yours, answer will be 1 as there is only one multiple of 4(i.e. 4 itself) that evenly divides 20. but i thnik it must include 8 also as it satisfies both the condition given in the problem statement.

t_tahasin + 1 comment Please read the problem description carefully. Specially the conditions.

- All elements in A are factors of x.
- x is a factor of all elements in B.

Now look at the condition-2, Do you think 8 is a factor of all elements in B{20, 40}?

Another thing, the answer for your test case will not be

**1**, it will be**2**as multiples are**4**and**20**(you excluded**20**).praveenbdj + 0 comments oh. my bad. thank you for clarification.

elvis_dukaj + 2 comments Great solution, an implementation in C++:

#include <vector> #include <iostream> #include <algorithm> #include <numeric> #include <iterator> using namespace std; int gcd(int num1, int num2) { auto divisor = min(num1, num2); for(; divisor > 0; --divisor) if ((num1 % divisor == 0) && (num2 % divisor == 0)) break; return divisor; } int gcd_element(const vector<int>& v) { return accumulate(begin(v), end(v), *begin(v), gcd); } int lcm(int num1, int num2) { return (num1 * num2) / gcd(num1, num2); } int lcm_element(const vector<int>& v) { return accumulate(begin(v), end(v), *begin(v), lcm); } int is_divisible(int num1, int num2) { return num1 % num2 == 0 ? 1 : 0; } int main() { int m, n; cin >> m >> n; vector<int> A(m); vector<int> B(n); copy_n(istream_iterator<int>(cin), m, begin(A)); copy_n(istream_iterator<int>(cin), n, begin(B)); auto lcmOfA = lcm_element(A); auto gcdOfB = gcd_element(B); auto counter = 0; auto multipleOfLcm = lcmOfA; while (multipleOfLcm <= gcdOfB) { counter += is_divisible(gcdOfB, multipleOfLcm); multipleOfLcm += lcmOfA; } cout << counter << endl; return 0; }

ScienceD + 2 comments 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; }

elvis_dukaj + 0 comments In this case I think is more readable non recursive solution:

vector<int> A(m); vector<int> B(n); /// [...] auto lcmOfA = lcm_element(A); auto gcdOfB = gcd_element(B); auto counter = 0; auto multipleOfLcm = lcmOfA; while (multipleOfLcm <= gcdOfB) { counter += is_divisible(gcdOfB, multipleOfLcm); multipleOfLcm += lcmOfA; }

positivedeist_07 + 0 comments Imma bit confused here. What do u do with the bitwise & operator?? And why do u add with the boolean value? I'm sorry if I sound dumb :( i'm new to DP. Could u pls explain ur code?

karthik1983_sbt + 0 comments Nice one

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

elvis_dukaj + 0 comments In this case I think is more readable non recursive solution:

vector<int> A(m); vector<int> B(n); /// [...] auto lcmOfA = lcm_element(A); auto gcdOfB = gcd_element(B); auto counter = 0; auto multipleOfLcm = lcmOfA; while (multipleOfLcm <= gcdOfB) { counter += is_divisible(gcdOfB, multipleOfLcm); multipleOfLcm += lcmOfA; }

baymaxneoxys + 1 comment What if LCM(A) = GCD(B)+1 ? or GCD(B) - LCM(A) <<<< LCM(A) ?

Also, step 3 seems to suggest that I must use brute force. Is that the best I can do? Or do we have a faster way to do that?

(Just curious)

t_tahasin + 0 comments For both cases

**LCM(A) = GCD(B)+1**and**GCD(B) - LCM(A) <<<< LCM(A)**the result would be 0.For step-3 you need to run a loop from

**LCM**upto**GCD**each time multiplying the**LCM**by 1,2,3.. so on. See the sudo code below.GCD%(LCM*i)==0, where i=1,2,3... until LCM*i<=GCM;

If you think running a loop means brute forcing, then yes you have to use brute force. :)

mihiraman + 0 comments [deleted]Nitishp24 + 0 comments Wow thats so simple.Thanks for the solution.

singhmanjeetn + 1 comment explation for 3rd line "Count the number of multiples of LCM that evenly divides the GCD."

t_tahasin + 1 comment Suppose

**L**is your calculated LCM of array**A**and**G**is your calulate GCD of array**B**. Then the result will be number of multiples of**L**which will evenly devides**G**. Here evenly devides meaning the remainder will be zero if you devide x by y.Pseudo code

count = 0; for i = 1 to L*i<=G if(G%(L*i) == 0) count = count+1; return count;

singhmanjeetn + 0 comments @t_tahasin thanks for the response, I underestand what you want to convey in that 3rd line, I was just curious to know why it is so, any mathematical proof or reason to support that line (I was not able to find how you reach to that)

__ptr + 0 comments Equivalently, do the same 1 and 2, check if lcm evenly divides gcd, then count the factors of gcd/lcm, otherwise 0.

main :: IO () countFac :: Int -> Int -> Int main = do getLine a_temp <- getLine let a = map read $ words a_temp :: [Int] b_temp <- getLine let b = map read $ words b_temp :: [Int] let l = foldl lcm (head a) (tail a) let g = foldl gcd (head b) (tail b) let s = g `div` l if s * l /= g then do print 0 return () else do print (countFac s 1) return () countFac n c | c > n `div` 2 = 1 | n `div` c * c == n = 1 + countFac n (c+1) | otherwise = countFac n (c+1)

tocshark + 0 comments i lke the prblem and salution

sankireddyvinee1 + 0 comments thats great idea.. thank a lot....

tocshark + 0 comments badhiya socha!

muromari5123 + 1 comment Ruby version.

def getTotalX(a, b) # Complete this function # 1. find the LCM of all the integers of array A. 最小公倍数 lcm1 = a.lcm # 2. find the GCD of all the integers of array B. 最大公約数 lcd1 = b.gcd # 3. Count the number of multiples of LCM that evenly divides the GCD. count = 0 for m in 1..100 do if (lcd1 % (lcm1 * m)) == 0 then count += 1 end end puts count end class Array def lcm self.inject{|a,b| a.lcm(b)} end def gcd self.inject{|a,b| a.gcd(b)} end end

haruken + 0 comments Ruby version in one line

def getTotalX(a, b) # Complete this function (1..b.min).to_a.reverse.select{|m| b.map{|bb| bb % m == 0}.all?}.select{|n| a.map{|aa| n % aa == 0}.all?}.count end

listensabchillh1 + 1 comment - Count the number of multiples of LCM that evenly divides the GCD.

why evenly?

t_tahasin + 0 comments Evenly divisible means the remainder will be 0 after division. If M evenly devides N then N % M == 0.

sportmew + 1 comment Can you explain what happens when there is a single element in A with value 1 and a single element in B with value 100?

t_tahasin + 1 comment See below explanation with your input.

Step-1:

**LCM**of array**A**will be**1**.Step-2:

**GCD**of array**B**will be**100**.Step-3: The multiples of LCM(1) that evenly devides GCD(100) are 1,2,4,5,10,20,25,50,100. So the answer will be 9.

Note: evenly divisible means the remainder will be 0 after division. If M evenly devides N then N % M == 0.

sportmew + 0 comments Thankyou for explaining in detail.

thelight_mn + 0 comments ty man.

Vinprogress + 0 comments Can you tell, how you came up with solution?

[deleted] + 0 comments 2 3 2 4 16 32 96 it will not pass this test case. You need to put last condition like lcm should evenly divide the gcd and gcd should evenly divisible by number between lcm and gcd.

mahendrakumar091 + 0 comments That's a great logic!

prickpunk + 0 comments Why count the number of multiples of LCM that evenly divides the GCD? Its enougth to intersect array of A and B (elements, that exists in both arrays)

codedeepesh + 0 comments hey if anyone is looking here a very basic c++ code in this code I used loops to first get all the elements in array that divide all the values between max of a and min of b

then I stored those a[]'s in new array that I again run a for loop to found count if all elelments in new array divide elements of array b

here is the code ` //code written on date:17 aug 2018 hacker rank between two sets problem

# include

using namespace std;

int getTotalX(int a [], int b [],int n ,int m) { int a_max=a[0],b_min=b[0];

`for(int i=0; i<n; i++) { if(a[i]>a_max) a_max=a[i]; } for(int j=0; j<m; j++) { if(b[j]<b_min) b_min=b[j]; }`

// cout<=a_max){

`for(int k=b_min; k>=a_max; k--) { int cnt=0; for(int i=0; i<n; i++ ) { if(k%a[i]==0) { cnt++; } //cout<<"count is "<<cnt<<endl; } if(cnt==n) { newarr[p]=k; //cout<<"arr[]: "<<newarr[p]<<","<<endl; p++; } }`

} /

*----------------------------------------------------------------------------*/ //cout<<"p:"<int finalcount=0; for(int i=0; i

`for (int j=0; j<m; j++) { if(b[j]%newarr[i]==0) cnt1++; } if(cnt1==m) finalcount++;`

}

//cout<<"finalcount"<

`return finalcount;`

}

int main() { int n,m; cin>>n>>m; int a[n],b[m]; for(int i=0; i

`cin>>a[i]; } for(int j=0; j<m; j++) { cin>>b[j]; }`

cout<

`return 0;`

}`

codedeepesh + 0 comments # include

using namespace std;

int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } int lcm(int x, int y ) {

`if(x==0) return 0; return (x*y)/gcd(x,y);`

}

int main() { int n,m; cin>>n>>m; int a[n],b[m];

`for(int i=0; i<n; i++) { cin>>a[i]; } for(int j=0; j<m; j++) { cin>>b[j]; } int x=a[0]; int y=b[0]; for(int i=0; i<n; i++) { x=lcm(x,a[i]); } for(int j=0; j<m; j++) { y=gcd(y,b[j]); } //cout<<x<<endl; //cout<<y<<endl; //count the multiples of lcm of a that divides gcd of b int k=1; int count=0; int num=x; while(x<=y) { if(y%(x)==0) count++; k++; x=num*k; }`

cout<

bbducs17 + 0 comments import java.io.

*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*;public class Solution {

`/* * Complete the getTotalX function below. */ static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } static int lcm(int a, int b) { return (a * b) / gcd(a, b); } static int getTotalX(int[] a, int[] b) { //llcm of a int num1 = a[0]; for (int i = 0; i < a.length; i++) { num1 = lcm(a[i], num1); } ///System.out.println(num1); // Gcd of b int num = b[0]; for (int i = 0; i < b.length; i++) { num = gcd(b[i], num); /// System.out.println(num); } int counter = 0; for(int i=1; i<= num/num1; i++){ if(num % (num1*i)==0) ++counter; } return counter; } private static final Scanner scan = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] nm = scan.nextLine().split(" "); int n = Integer.parseInt(nm[0].trim()); int m = Integer.parseInt(nm[1].trim()); int[] a = new int[n]; String[] aItems = scan.nextLine().split(" "); for (int aItr = 0; aItr < n; aItr++) { int aItem = Integer.parseInt(aItems[aItr].trim()); a[aItr] = aItem; } int[] b = new int[m]; String[] bItems = scan.nextLine().split(" "); for (int bItr = 0; bItr < m; bItr++) { int bItem = Integer.parseInt(bItems[bItr].trim()); b[bItr] = bItem; } int total = getTotalX(a, b); bw.write(String.valueOf(total)); bw.newLine(); bw.close(); }`

}

tordjarv + 0 comments I'm not so sure that that solution has a time complexity of O(n log(n)). Sure the computation time will depend on the size of A, but also on the size of B, the size of the elements in A and B, and the number of multiples of lcm(A) less than or equal to gcd(B).

kushagrapathak91 + 0 comments very very big thank to you sir

foxtrotsk + 0 comments Passes all the test cases

import java.util.*; import java.math.*; public class betweenSets { //Finding LCM of ARRAY a public static int lcm(int a,int b) { return (Math.abs(a*b))/gcd(a,b); } public static int findLcm(int[]a,int size) { int result1=a[0]; for(int i=1;i<size;i++) { result1=lcm(a[i],result1); } return result1; } //Finding GCD of ARRAY b public static int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } public static int findGcd(int[]b,int size2) { int result=b[0]; for(int i=1;i<size2;i++) { result=gcd(b[i],result); } return result; } public static void main(String args[]) { Scanner s=new Scanner(System.in); int size=s.nextInt();//Size of Array a int size2=s.nextInt();//Size of Array b int[]a=new int[size]; int[]b=new int[size2]; for(int i=0;i<size;i++) { a[i]=s.nextInt(); } for(int i=0;i<size2;i++) { b[i]=s.nextInt(); } int L=findLcm(a,size);//LCM of a int G=findGcd(b,size2);//GCD of b // System.out.println(L); //System.out.println(G); int count=0; // Count the number of multiples of LCM that evenly divides the GCD for(int i=L;i<=G;i+=L) { if(G%i==0) count++; } System.out.println(count); } }

Thinkster + 0 comments Ruby implementation:

def getTotalX(a, b) lcm, gcd = a.reduce(:lcm), b.reduce(:gcd) return lcm.step(gcd, lcm).select{|i| gcd % i === 0}.to_a.length end

am495399 + 1 comment **In PYTHON based on your logic**def getTotalX(a, b): # First LCM of a lcm = [] x = 1 while x <= min(b): for y in a: if x%y!=0: x+=1 break else: lcm.append(x) x+=1 #HCF of b hcf = 1 for x in range(1,min(b)+1): for y in b: if y%x!=0: break else: hcf=x # Final check count = len(lcm) for x in lcm: if hcf%x!=0: count-=1 return count

long but really basic

kharsharaman97 + 0 comments can you explain this logic in detail

bommadinesh + 0 comments eplain the problem,but dont show the code it may spoil our coding skills.

bommadinesh + 0 comments sorry this message is not for you

andreaswilli + 1 comment JS implementation of this solution:

function getTotalX(a, b) { return [...new Array(Math.floor(gcd(b) / lcm(a)))] .map((_, i) => lcm(a) * (i + 1)) .filter(a => gcd(b) % a === 0) .length; } function gcd2(a, b) { if (!b) return a; return gcd2(b, a % b); } function lcm2(a, b) { return a * b / gcd2(a, b); } function gcd(arr) { return arr.reduce(gcd2); } function lcm(arr) { return arr.reduce(lcm2); }

rob_abcba + 0 comments Yes, Makes sense that since we are given arrays, that we should first try to use array methods like .map, .filter, and .reduce to solve it in a functional programming paradigm. I think you will get a lot of Likes on YouTube if you find some time to post a video explaining all the steps in your code above. :-)

speedmonster + 0 comments can u explain how this is o(nlog(n))??

xiaoliji + 0 comments python 3 lines.

def getTotalX(a, b): g = reduce(math.gcd, b) lcm = reduce(lambda x, y: (x * y) // math.gcd(x, y), a) return sum(g%l==0 for l in range(lcm, g+1, lcm))

lin_dewei1 + 0 comments Question was a bit difficult to understand. I was able to figure out that you wanted to get the LCM of all integers of A, but for this, I thought that since 2 is a factor of 20, 30, and 12 the output would be 3.

A = [2] B = [20,30,12]

Once you wrote it like this, I was able to fix the solution.

anirudh_0831 + 0 comments couldn't find the explaination as to why the steps mentioned in the top comment works the way it does.

So here's an explaination https://coderinme.com/between-two-sets-hackerrank-problem-solution/

prernabharti66 + 0 comments int n=a.length,m=b.length; int num=a[n-1]; int count=0,flag; while(num<=b[0]){ flag=0; for(int i=0;i

harshnagpal10 + 0 comments nice.

Grand_Priest + 0 comments well i used a different method and it passed all the test cases however, your solution is awesome. It would be really helpful if you can provide any proof or explaination of your solution

osama119786 + 0 comments 3 2 2 3 6 42 84 why this test case have "2" as correct answer ? after doing by above method it shoud be 5 . sorry , if i am wrong pls correct me .

zidani_bill + 0 comments I think that a brute force solution will be less complex in time (and also in line of codes) starting from last element of a until first element of b and check for every element whether it fits the conditions.

abhik0301 + 0 comments thanks for this solution, but how did u find it out???? @t_tahasin

kamalnathlp + 0 comments why we are approaching with lcm and gcd method?

exaltedtoast + 0 comments It can be reduced to O(n) by, instead of counting all multiples of LCM in GCD, using a divisor counting function on (gcd/lcm). A naive implementation of the latter is often O(sqrt(n)) with room for optimization, and you get O(n+sqrt(n)) = O(n).

kasured + 1 comment Implemented the algorithm in a similar way, however, I am not quite sure I understand your time complexity analysis. What is

**n**in your comment?One can calculate lcm/gcd of two numbers in O(n^2), where

*n is the number of bits*(simplest Euclidian algorithm). But given the fact that we have fixed bit size integers we might consider this be a constant, say*C1*Now, lets assume that LA - is the length of array A, and LB - length of array B, them the overal time complexity will be O(C1*(LA + LB) + ((GCD(B) / LCM(A))). We might probabably want to discard the constant factor for counting multiples because we have restriction of numbers being less than 100, however for a more general case and huge numbers this might be a factor

t_tahasin + 0 comments Go through the below link. You might get an explanation regarding time complexity analyisis.

2*n*log(n) is counted as n*log(n)

tushar_gadhiya37 + 0 comments `simple python code: count = 0 for i in range(max(a),min(b)+1): if all([i%x == 0 for x in a]) and all([x%i == 0 for x in b]): count += 1 return count`

amitojsingh_edc1 + 0 comments How you deduced this logic. I want to know thought process.

gzslw50 + 0 comments Thanks so much for explaining, I am completely lost with the wording of the problem ☹

amitkumar9798411 + 0 comments # > a sweet and simple ans

int getTotalX(vector a, vector b) { int gcd(int a,int b) { if(a==0) return b; return gcd(b%a,a); }

`int lcm=a[0],hcf=b[0],ans=0; for( auto l:a) lcm=(lcm*l)/(gcd(l,lcm)); for(auto m:b) hcf=gcd(hcf,m); for(int i=1;i>=0;i++) {if((i*lcm)>hcf) break; if((hcf%(i*lcm))==0) ans++; } return ans;`

}

shaurya_src + 0 comments [deleted]shaurya_src + 0 comments For python 3.x :

from math import gcd from functools import reduce

n, m = map(int, input().split()) a = list(map(int, input().strip().split())) b = list(map(int, input().strip().split()))

def lcm_val(n): lcm = n[0] for i in n[1:]: lcm = lcm*i//gcd(lcm, i) return lcm

def gcd_val(m): hcf = reduce(gcd, m) return hcf

x, y = lcm_val(a), gcd_val(b) c = 0

for i in range(1, y//x + 1): if y % (x*i) == 0: c += 1

print(c)

premcodechef123 + 0 comments nice

diego_amicabile + 5 comments I found this outrageously difficult for being "easy" and I would have not even begun to understand what I was supposed to do without reading the discussions. "Factor" ? "Between two sets"? Why not call things by their name : GCD, LCM ?

Congratulations to those who solved this problem without help, this was way over my head.karayv + 0 comments Considewring the boundaries you can solve the task with simple brudeforce solution. Guys are just having fun here with GCD and LCM.

htacla + 0 comments Just like karayv said, you could bruteforce it by testing the condition against all the integers in a small range set by the inputs - like so:

int getTotalX(vector <int> a, vector <int> b) { // Range of int goes from the LAST element of A to the LAST of B // (some have said it should end on the FIRST of B, but I played it safely) int start = a.back(), end = b.back(); int count = 0; for(int x = start; x <= end; x++){ // Booleans to test whether X fulfills condition bool a_pass = true, b_pass = true; for(const auto &ai : a){ if(x % ai != 0){ // If it doesn't, set flag and break out of A loop a_pass = false; break; } } // If A didn't complete successfully, continue with next integer if(!a_pass) continue; for(const auto &bi : b){ if(bi % x != 0){ // Idem A loop b_pass = false; break; } } // If both test were OK, count that integer if(a_pass && b_pass) count++; } return count; }

Arguably, the GCD/LCM approach is more efficient if done correctly (around

*O(*vs this**n/log(n)**)*O(*), yet for such a small range it shouldn't be much of a problem.**n^2**)KeithDC + 0 comments I would say it was definitely challenging. Maybe the easy side of hard; not expert.

Although I thought I had it figured out early on, I got caught up as I always do, having to adjust for this, then having to adjust for that... and then, the edge cases. (case #3 taught me I missed testing the left (a) side power/mod while also testing the b-side factors.)

JellyKid + 0 comments That's the problem with using problems like these in an interview. There's always a trick to them. I guarantee that no one in here devised the GCD/LCM method by themselves in their solutions. The algorithms were figured out over spans of decades by different mathematicians.

ritzerk + 1 comment For those who are still trying to understand the question...

You run through some integers to check them against the arrays, whether they match the expecations as the two given. When they do, these integers become the answer.

So lets say we are investigating integer X. The integer X has to be

--> Perfectly divisible by all elements in the first array. If you divide X by any integer from the array, you would need to get a full number. This by definition means that the elements of such array would be factors of X. Such condition can be checked by the MOD function, which returns the remainder of division, where

**X % Array1Element = 0**--> Perfectly divide into all elements in the second array. Each element divided by X would produce an integer result. Such that

**Array2Element % X = 0**jinjian_tan + 0 comments Thank you!

Worldfrom6feet + 3 comments For all those guys like me who found this question difficult to understand, here's the simple explanation i got after searching for decades.

**1. Find LCM of the first array a. 2.Find GCD / HCF of the second array b. 3.Find all the multiples of LCM up to GCD, which divides the GCD evenly.**For Example: Here, In the given sample Input, The LCM of array a would be

**4**and the GCD of the array b would be**16**. Now, Find all Multiples of 4,(like 4,8,12,16,...) upto 16, such that,**(16%multiple_of_4_here) should be 0.**Here, 16%4=0 -----> count=1 (suppose this variable.) 16%8=0 -----> count=2 16%12!=0 ---> count=2 16%16=0 ---> count=3.Thus, The answer is 3. Hope this helped you.

flemos13 + 0 comments Thank you for your awesome explanation, it certainly helped me!

Thinkster + 1 comment Ruby implementation:

def getTotalX(a, b) lcm, gcd = a.reduce(:lcm), b.reduce(:gcd) return lcm.step(gcd, lcm).select{|i| gcd % i === 0}.to_a.length end

ashok821822 + 0 comments Can u explain it.

Shaikatpal56 + 0 comments

Sort 1509 Discussions, By:

Please Login in order to post a comment