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
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
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
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;
}
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 :).
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.
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.
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
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:
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";
}
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;
};
}
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
thank you so much for your advise askarovdaulet
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.
It should not go out of range. Use { function lcm(arr){ var multiples = {}, factors, f = [], lcm = 1;
}
function primes(number) { number = Math.abs(number); var divider = 2, dividend, factors = [];
}
function countElement(haystack, needle) { var count = 0; for(var i of haystack){ if(JSON.stringify(i) == JSON.stringify(needle)) count++; } return count; } }
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
ugly code
public static int getTotalX(List a, List b) {
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?
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
Nice logic!
The same logic in C#:
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.
" C# " for everyone CTRL+F-ing.
//Stored a.Max() and b.Min() as dsgarg71 suggested below :).
Very nice optimization! I really was not realized it. Thanks. :)
Thanks :). dsarg71 found another neat optimization. I've added that as well.
Wow It did the magic. Thanks
Thats n^3, Why not to store a.Max/b.Min and other such stuff once got so that their compute does not repeat.
You're right, the computation does indeed get repeated, I've changed the code accordingly. Good eye!
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.
its all about mathematics people will learn eventually
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.
This is a fucking work of art.
nice job
why "i x nmax"?
can u explain the for loop range??
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.
whenever I see variables like a,b,x,r,i,k etc, I get a near heart attack.
RIP
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. */
what is 101 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?
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:
}
Same solution using Java8:
Python 3 ::
Awesome.. So clear and simple