We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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_LCM
Use Java 8 streams for shorter and more concise code. Specifically, use the reduce function since "reduction operations parallelize more gracefully" - Oracle Documentation.
importjava.util.Scanner;importjava.util.Arrays;publicclassSolution{publicstaticvoidmain(String[]args){/* Read and save input */Scannerscan=newScanner(System.in);intn=scan.nextInt();intm=scan.nextInt();int[]arrayA=newint[n];for(inti=0;i<n;i++){arrayA[i]=scan.nextInt();}int[]arrayB=newint[m];for(inti=0;i<m;i++){arrayB[i]=scan.nextInt();}scan.close();/* Find LCM of arrayA. Find GCD of arrayB */intA_LCM=lcm(arrayA);intB_GCD=gcd(arrayB);/* Calculate # of integers "between" arrayA and arrayB */intcount=(B_GCD%A_LCM==0)?numDivisors(B_GCD/A_LCM):0;System.out.println(count);}privatestaticintgcd(inta,intb){// Euclid's GCD Algorithmwhile(b!=0){inttemp=b;b=a%b;a=temp;}returna;}privatestaticintlcm(inta,intb){return(a*b)/gcd(a,b);}privatestaticintgcd(int[]array){returnArrays.stream(array).reduce(array[0],(a,b)->gcd(a,b));}privatestaticintlcm(int[]array){returnArrays.stream(array).reduce(array[0],(a,b)->lcm(a,b));}privatestaticintnumDivisors(intn){intcount=0;intsqrt=(int)Math.sqrt(n);for(inti=1;i<=sqrt;i++){if(n%i==0){// if "i" is a divisorcount+=2;// account for both divisors}}/* If sqrt is a divisor, we should only count it once */if(sqrt*sqrt==n){count--;}returncount;}}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.
Between Two Sets
You are viewing a single comment's thread. Return to all 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_LCM
Use 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.
By the way,
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.