# Between Two Sets

# Between Two Sets

t_tahasin + 29 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.- MB
Bmukhtar + 14 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]- SK
samikshakumari27 + 0 comments why did you multiply 2 with the i in the loop ?

- DA
askarovdaulet + 4 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 + 1 comment "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).

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

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

- AS
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.

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

- [U
[deleted] + 0 comments [deleted] __grj + 0 comments [deleted]KeyurPotdar + 0 comments [deleted]azicon + 1 comment 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

- IG
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.

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

- IG
ishita_ghosh + 1 comment ty

azicon + 0 comments you are welcome

- AA
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.

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

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

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

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

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

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;

- VB
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?

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

NicolasBi + 8 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)

- DA
askarovdaulet + 3 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

- J
kanabos + 0 comments 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))

- RQ
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)

- RQ
P1zzAdr0hn3 + 4 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)

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

- RQ
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.

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

paul_schmeida + 1 comment It's asymptotic actually :)

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

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

MatricksDecoder + 0 comments 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)]))

- AJ
ash_jo4444 + 0 comments Awesome solution !!

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

- RQ
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)."

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

- CZ
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?

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

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

- AA
anurag12345 + 0 comments Awesome bro

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

if hold > 0:

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

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

- AK
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.

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

LittleHacker12 + 0 comments [deleted]LittleHacker12 + 1 comment I already passed the step 1 and step 2 (not quite sure if it's right tho) I don't understand what you mean in step 3, can someone explain?

int gcd(int p, int q){ int e; if(q==0) return p; else return gcd(q,p%q); } int lcm(int x,int y){ int e; e=gcd(x,y); return (x*y)/e; } int main(){ int a,b,f,g; cin>>a>>b; int c[a],d[b]; for(int i=0; i<a; i++){ cin>>c[i]; if(i!=0) f=lcm(c[i-1],c[i]); } for(int i=0; i<b; i++){ cin>>d[i]; if(i!=0) g=gcd(d[i-1],d[i]); } return 0; }

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

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

- JS
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!

- YS
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.

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

- YS
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.

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

- DA
askarovdaulet + 0 comments 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))

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

- [U
[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.

- ED
elvis_dukaj + 1 comment 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; }

- ED
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?

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

- ED
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)

- RP
__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)

- SK
tocshark + 0 comments i lke the prblem and salution

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

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

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

- HB
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.

- AK
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.

- AK
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?

- DA
dilipagarwal01 + 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.

diego_amicabile + 3 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.

- H
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.)

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

- AG
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.- AV
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.

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

- SB
svbi_2905 + 0 comments i tried the same way in c++ but i was getting time out erreoe

- LO
LamaO3 + 0 comments Man , that is awesome

- JD
I0000 + 5 comments Java solution. Iterate through the numbers between max in A and min in B, sum up the modulus (since for something to be a factor modulus has to equal zero), and count the number of numbers that are between the two sets.

Arrays.sort(a); Arrays.sort(b); int lower_bound = a[n-1]; int upper_bound = b[0]; int count_x = 0; for(int i = lower_bound; i <= upper_bound; i++){ int sum_mod = 0; for(int j = 0; j < n; j++){ sum_mod += i % a[j]; } for(int k = 0; k < m; k++){ sum_mod += b[k] % i; } if(sum_mod == 0) ++count_x; } System.out.print(count_x);

kaveti0 + 0 comments lower_bound=a[0];

upper_bound=b[m-1]; More or less the same but this also works.sushant55252 + 0 comments [deleted]binayagarwal20 + 0 comments [deleted]geekytroy + 0 comments [deleted]- EA
sicter + 0 comments Note this is sorting a and b (which takes O(n log n)) solely for the sake of getting the max and min in contant time. This can be improved by linearly searching for the max/min in O(n)

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

- W
wolfahoward + 0 comments 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.

anil_nara + 3 comments In Python 3!

n,m = [int(i) for i in input().strip().split(' ')] a = [int(a_temp) for a_temp in input().strip().split(' ')] b = [int(b_temp) for b_temp in input().strip().split(' ')] result = 0 for x in range(max(a), min(b)+1): divideA = [x%j!=0 for j in a] divideB = [j%x!=0 for j in b] if sum(divideA)==0 and sum(divideB)==0: result += 1 print(result)

anil_nara + 0 comments To be compared to what I found in C++ ;-)

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n, m; cin>>n>>m; vector<int> a, b; for (int i=0; i<n; ++i){ int value; cin>>value; a.push_back(value); } for (int i=0; i<m; ++i){ int value; cin>>value; b.push_back(value); } int maxA = *max_element(a.begin(), a.end()); int minB = *min_element(b.begin(), b.end()); int numBetweens = 0; for (int x=maxA; x<=minB; ++x){ bool cont = true; for (int i=0; i<n; ++i){ if (x % a[i] != 0){ cont = false; } } if (cont){ for (int j=0; j<m; ++j){ if (b[j] % x != 0){ cont = false; } } } if (cont){ numBetweens += 1; } } cout<<numBetweens; return 0; }

- GW
greg_walsh + 1 comment Very neat, good to include the range(max(a), min(b)+1) to bound the search for x's, and exclude candidates from both sides with a single parent loop. An idea for optimisation...

max(a) is odd, min(b) is odd, just search odds

max(a) is odd, min(b) is even, search all

max(a) is even, min(b) is even, just search evens

max(a) is even, min(b) is odd, don't search anything

I wonder if there are others.

- JS
jeschlegel84 + 0 comments You could use range(max(a), min(b)+1, max(a)) because max(a) will have to be a factor

- BL
logube + 0 comments Could you please explain it for common mortals with tiny brains? :-( Thanks

saipriyaagni + 4 comments C++ code passes all testcases.

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; int main(){ int n;int i = 0; int min_a = 100; int m;int factor = 0; int max_b = 0; cin >> n >> m; vector<int> a(n); for(int a_i = 0;a_i < n;a_i++){ cin >> a[a_i]; if( a[a_i] <= min_a ) min_a = a[a_i]; } vector<int> b(m); for(int b_i = 0;b_i < m;b_i++){ cin >> b[b_i]; if(b[b_i] > max_b) max_b = b[b_i]; } for(int i = min_a; i <= max_b ;++i ) { int sum = 0; for (int j = 0; j < n;j++) sum +=i%a[j]; for(int k = 0; k <m ;k++) sum +=b[k]%i; if(sum == 0) ++factor; } cout <<factor; return 0; }

- SK
Shyam_Shenoy + 0 comments [deleted] - SK
Shyam_Shenoy + 0 comments Really good solution. Although a little modification can be done to make it run faster. You need to calculate max_a and min_b instead and only need to care about the multiples of max_a instead of going through all the numbers in between.

#include <bits/stdc++.h> using namespace std; int main() { int n; int min_b = 100; int m; int factor = 0; int max_a = 0; cin >> n >> m; vector<int> a(n); for(int a_i = 0;a_i < n;a_i++){ cin >> a[a_i]; if( a[a_i] > max_a ) max_a = a[a_i]; } vector<int> b(m); for(int b_i = 0;b_i < m;b_i++){ cin >> b[b_i]; if(b[b_i] < min_b) min_b = b[b_i]; } for(int i = 1; i <= min_b/max_a ;++i ) { int sum = 0; for (int j = 0; j < n;j++) sum +=(i*max_a)%a[j]; for(int k = 0; k <m ;k++) sum +=b[k]%(i*max_a); if(sum == 0) ++factor; } cout <<factor; return 0; }

- DM
dahveed + 0 comments Insanely good solution and out of the box. I'm seriously impressed. Really nice work.

- ST
sunny_tiwari505 + 0 comments awesome approach.....

- JB
jjbrimil + 1 comment c#:

static void Main(String[] args) { string[] tokens_n = Console.ReadLine().Split(' '); int n = Convert.ToInt32(tokens_n[0]); int m = Convert.ToInt32(tokens_n[1]); string[] a_temp = Console.ReadLine().Split(' '); int[] a = Array.ConvertAll(a_temp,Int32.Parse); string[] b_temp = Console.ReadLine().Split(' '); int[] b = Array.ConvertAll(b_temp,Int32.Parse); var aLCM = a.Aggregate(LCM); var bGCD = b.Aggregate(GCD); Console.WriteLine( Enumerable.Range(1,bGCD/aLCM) .Where(i=> bGCD % (aLCM*i) == 0).Count()); } static int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); } static int LCM(int a, int b) { var k=GCD(a,b); a/=k; return a*b; }

rodrigoramirez93 + 0 comments WOW. Great work

rshaghoulian + 3 comments ### Efficient Java solution

1) find A_LCM, which represents the LCM of all integers in array A

2) find B_GCD, which represents the GCD of all the integers in array B

3) Print the number of multiples of A_LCM that are divisors of B_GCD. This can be done efficiently by calculating the number of divisors of B_GCD/A_LCMUse Euclid's GCD algorithm to efficiently calculate the GCD

Use Java 8 streams for shorter and more concise code. Specifically, use the reduce function since "reduction operations parallelize more gracefully" - Oracle Documentation.

import java.util.Scanner; import java.util.Arrays; public class Solution { public static void main(String[] args) { /* Read and save input */ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); int [] arrayA = new int[n]; for (int i = 0; i < n; i++) { arrayA[i] = scan.nextInt(); } int [] arrayB = new int[m]; for (int i = 0; i < m; i++) { arrayB[i] = scan.nextInt(); } scan.close(); /* Find LCM of arrayA. Find GCD of arrayB */ int A_LCM = lcm(arrayA); int B_GCD = gcd(arrayB); /* Calculate # of integers "between" arrayA and arrayB */ int count = (B_GCD % A_LCM == 0) ? numDivisors(B_GCD / A_LCM) : 0; System.out.println(count); } private static int gcd(int a, int b) { // Euclid's GCD Algorithm while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } private static int lcm(int a, int b) { return (a * b) / gcd(a, b); } private static int gcd(int [] array) { return Arrays.stream(array).reduce(array[0], (a, b) -> gcd(a, b)); } private static int lcm(int [] array) { return Arrays.stream(array).reduce(array[0], (a, b) -> lcm(a, b)); } private static int numDivisors(int n) { int count = 0; int sqrt = (int) Math.sqrt(n); for (int i = 1; i <= sqrt; i++) { if (n % i == 0) { // if "i" is a divisor count += 2; // account for both divisors } } /* If sqrt is a divisor, we should only count it once */ if (sqrt * sqrt == n) { count--; } return count; } } b)); }

By the way,

(a, b) -> lcm(a, b)

is just a representation of a function that takes 2 parameters and returns the LCM of the 2 parameters. These are known as lambda expressions.

From my HackerRank solutions.

Let me know if you have any questions.

- FF
FilipF + 1 comment Very nice! Without the parallelization, Test Case #1 can time out. I think there's a handful of similar interesting observations about speed.

- The arrays can be skipped, since the GCD and LCM can be calculated on the fly. Streams can still be used, just by feeding the integers into the stream directly, no?

- It seems worth testing that the intermediate LCMs are still <= 100, because in that case the algorithm can terminate early. Especially since if there's more than one distinct prime factor > 7 among the A_n's, the LCM will definitely be over one hundred.

- Ditto for testing that the GCD isn't smaller than the LCM.

- Finally, finding the number of values that are in between A and B is equivalent to finding out how many factors there are for`GCD_b/LCM_a`

. And for that, at worst we only need to test 2 thru 10 as divisors. Pretty cheap!I wonder if there's an efficient way to calculate the LCM of a set of numbers, without finding the intermediate LCMs along the way. Feels like there's some redundant calculations going on.

Thanks for indulging the musings, cheers!

rshaghoulian + 0 comments Excellent points!

Creating an IntStream from the input would be cool but I'm not sure how to do it since InputStream from Java 1.0 is much different than IntStream from Java 1.8.

I updated the code to take into account your suggestion of finding factors of B_GCD/A_LCM. I don't use the upper-bound of 100 since i want to keep solution general.

Finding the LCM of a set of numbers efficiently would also be cool and would make Euclid proud.

Thanks for the tips.

jfranc01 + 1 comment Can you please explain what the reduce it doing here? I cannot understand the purpose of it.

rshaghoulian + 0 comments This is tough to explain. Let's say we have array {2, 3, 4, 1}. Let's say we have a "lambda" function that is

(a, b) -> a * b

When we use reduce, we traverse the array left to right. It takes each adjacent pair and multiplies it together while going left to right. So we get 2 * 3 = 6. Then it takes the 6 and multiplies it by 4, and we get 24. Then we do 24 * 1 and get 24.

So basically, it multiplies all the elements in the array together, by going left to right.

Now if instead of multiplication, if we have LCM, it does LCM(2, 3). It takes that result, and does LCM of that result with 4. Then it takes that result, and does LCM of that with 1.

If that made no sense, try reading about "lambda functions" in Java.

- [U
[deleted] + 0 comments You can replace labda with method reference.

kuldeep_daftary + 2 comments This is how I solved it in JS

function getTotalX(a, b) { let validX = []; const minA = Math.min(...a); const maxB = Math.max(...b); const isFactorOf = (arrItem, x) => x % arrItem === 0; const isFactorFor = (arrItem, x) => arrItem % x === 0; for(x = minA; x <= maxB; x++) { if (a.every(av => isFactorOf(av, x))) { if(b.every(bv => isFactorFor(bv, x))) { validX.push(x); } } } return validX.length; }

- GM
gabimoncha + 0 comments nice

- MK
mrunal_roy + 0 comments Work perfectly.

Sort 652 Discussions, By:

Please Login in order to post a comment