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.
publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();intm=in.nextInt();int[]a=newint[n];for(inta_i=0;a_i<n;a_i++){a[a_i]=in.nextInt();}int[]b=newint[m];for(intb_i=0;b_i<m;b_i++){b[b_i]=in.nextInt();}intf=lcm(a);intl=gcd(b);intcount=0;for(inti=f,j=2;i<=l;i=f*j,j++){if(l%i==0){count++;}}System.out.println(count);}privatestaticintgcd(inta,intb){while(b>0){inttemp=b;b=a%b;// % is remaindera=temp;}returna;}privatestaticintgcd(int[]input){intresult=input[0];for(inti=1;i<input.length;i++){result=gcd(result,input[i]);}returnresult;}privatestaticintlcm(inta,intb){returna*(b/gcd(a,b));}privatestaticintlcm(int[]input){intresult=input[0];for(inti=1;i<input.length;i++){result=lcm(result,input[i]);}returnresult;}
"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.
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.
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.
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
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.
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
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
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.
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();
}
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;
}
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
Between Two Sets
You are viewing a single comment's thread. Return to all comments →
like this one:
why did you multiply 2 with the i in the loop ?
why not
instead of
? Otherwise a very nice solution :)
"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.
How exactly is one different from the other?
My approach was as follows:
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.
Another suggestion to reduce the number of loop iterations
then double the count and add 1 if i*i==l
For the problem's testcase (f=4, l=16), won't your loop give count as 1 ?
why is it i*i?
because the value of i will be getting doubled for getting next factor easily.
i can only be multiples of lcm(a), that is why j starts at 2 and increases
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
for this case, why is lcm coming negative?
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.
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?
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
ty
you are welcome
yeah i too feel that hkrnk has poor tstcases
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.
copy paste maar dia bhai
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
sahi bola, tera jaisa kahan hi h...yahan koi only u will get 50 lakh i know!!
ye le solution samajh maine khudne banaya hai 2 ghante baith kar tu bhi bana saktaa hai agar hai himmat
Hi Rajat, can you please tell me about significance of "j"?
@rajat_yadav ye le.. tere wale se thoda easy hai
This is a very lengthy approach to the problem.
small
Could you explain what exactly is going on with this?
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
Small
i am not getting the logic can you please explain?
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..
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;
}
That makes it very easy for me.
@gkjha009 -- This is really good.
i think u shouldn't compute numberIsMultipleOfAll if allElementsAreMultiple is false
This is a great solution. I implemented it in Swift
This is a fucking work of art.
nice job
why "i x nmax"?
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.
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. */
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 {
}
Redundant memory allocation. There is no need to use arrays.
Here i wrote the code without using any array or vector
i didnt get why j=2 in this line bellow
could someone clarify me?
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]; }
How does this for loop works?
for(int i = f, j =2; i<=l; i=f*j,j++)
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
I have the same solution but i don't want the complexity is O(nlogn). can explain?