# Between Two Sets

# Between Two Sets

t_tahasin + 53 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 + 21 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 + 2 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 + 0 comments 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).

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.

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 + 0 comments For the problem's testcase (f=4, l=16), won't your loop give count as 1 ?

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

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 + 5 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 + 4 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 + 2 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.

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

iamkdm + 0 comments nice job

max_aka21 + 0 comments why "i x nmax"?

pathansuhana969 + 0 comments can u explain the for loop range??

evan51 + 1 comment 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

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 + 0 comments 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

lakshmi_koppara1 + 0 comments Awesome.. So clear and simple

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] + 4 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!

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 + 0 comments **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

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 + 0 comments 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); }

ashwinkumar_cn15 + 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?

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 + 0 comments 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**

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

Shaikatpal56 + 0 comments Hey!!! Nice Explanation...

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

aguenet + 0 comments [deleted]

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.

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

zubie7a + 5 comments Python with comprehension lists, for each number between max(setA) and min(setB), it will create a list that will hold boolean values, and 'all' checks that all the boolean values in a list are true.

lenA, lenB = map(int, raw_input().split()) setA = map(int, raw_input().split()) setB = map(int, raw_input().split()) maxA = max(setA) minB = min(setB) count = 0 for num in range(maxA, minB + 1): left = all([num % numA == 0 for numA in setA]) right = all([numB % num == 0 for numB in setB]) count += left*right print count

wolfahoward + 1 comment Was unaware of the all function. I was trying something similar to this with list comprehensions nested in a for loop, but I was removing options from a list within the range. I understood the question, but had no concept of the methods I should use to compare every element returning True. Appreciate the knowledge. I agree with the commenter below, found this pretty difficult.

luboyswag + 0 comments Here is a documentation defintion from Python that defines the all and any function. Pretty useful.

anishshanbhag15 + 0 comments [deleted]conquesteboigbe1 + 1 comment what is numA?

sarthakbpandey11 + 0 comments it's a temporary variable created while using "For Loop" to store all the iterable objects. Hope that makes sense.

thonagan + 0 comments Why is the range between maxA and minB?

william_belanger + 1 comment def getTotalX(a, b): return len([1 for i in range(max(a),min(b)+1) if all([i%j==0 for j in a]) and all([j%i==0 for j in b])])

brepese + 0 comments Beautiful.

Gloud + 5 comments **My javascript solution:**function getTotalX(a, b) { let validCount = 0; for (let x = 1; x <= 100; x++) { if (a.every(int => (x % int == 0))) { if (b.every(int => (int % x == 0))) { validCount++; } } } return validCount; }

1988_domi + 2 comments Thats one of the most elegant solutions I have ever seen but can you explain to a novice what (a.every(int => (x % int == 0))) means?

wangatqueens + 0 comments This is brilliant! Thanks!

apolo4pena + 2 comments This might be a silly question but why

`x <= 100`

?s_hong35 + 1 comment this is based on the constraints of the problem. we are told that each value in both arrays are between 1 < x <= 100

apolo4pena + 0 comments ah yes, thanks. I am not use to seeing the constraints accounted for in the code like that.

ridwan_taza + 0 comments You're right, why x <= 100? Excution time may be reduced using max = Math.max(...b) instead of 100 ...

for x > max => b.every(int => (int % x == 0)) return false

c_day + 0 comments My favorite solution although it might take awhile to compile with different

Sort 1207 Discussions, By:

Please Login in order to post a comment