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.

Thank you for your solution, you helped me produce this oversized Python 3 code :

#!/bin/python3importsysfromfunctoolsimportreducedeflcm(a:int,b:int)->int:returna*b//gcd(a,b)deflcm_list(lst:list)->int:returnreduce(lcm,lst)defgcd(a:int,b:int)->int:whilea%b!=0:a,b=b,(a%b)returnbdefgcd_list(lst:list)->int:returnreduce(gcd,lst)defevenly_divides(number:int,divisor:int)->bool:return(number%divisor)==0defget_input():n,m=input().strip().split()n,m=[int(n),int(m)]a=[int(a_temp)fora_tempininput().strip().split()]b=[int(b_temp)forb_tempininput().strip().split()]returnn,m,a,bdefmain():n,m,a,b=get_input()# Find LCM of all integers of alcm_value=lcm_list(a)# Find GCD of all integers of bgcd_value=gcd_list(b)# Count the number of multiples of LCM that evenly divides the GCD.counter=0multiple_of_lcm=lcm_valuewhilemultiple_of_lcm<=gcd_value:ifevenly_divides(gcd_value,multiple_of_lcm):counter+=1multiple_of_lcm+=lcm_valueprint(counter)if__name__=="__main__":main()

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

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

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

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.

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

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

## Between Two Sets

You are viewing a single comment's thread. Return to all comments →

Thank you for your solution, you helped me produce this oversized Python 3 code :

perhaps easier to understand, but your organization is on point. Uses built-in gcd:

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 :)Damn this is nice.

Nice

Not a big change but you can iterate less times:

1 is redundant. just

Awesome

Note for python3.7:

`DeprecationWarning: fractions.gcd() is deprecated. Use math.gcd() instead.`

3 for loops = O(n^3)

Yeah thats not nice... Your approach using lists and all() is much more elegant.

amazing way, but would this be O^2 ??

i think its O(2n^2)

O(2n^2) is supposed to be O(n^2). Constants aren't taken into account.

Asymptomatic complexity... i think now i got it :D

It's asymptotic actually :)

:D I knew it was something like that.

can you test this i/p: 3 2 4 8 12 12 24

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

surely should be min(b)+1 not max(b)+1

Awesome solution !!

Superb Dude!!

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!

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

for, for would be O(n^2) but we have for, for and for O(2n^2)

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

... you're right^^

its most lucid and probably the best algorithm ! Thanks. it made me understand the concept.

your program has one error... it is not compile

What is this syntax?

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.

Function annotations https://www.python.org/dev/peps/pep-3107/

Here is smaller code bro,

Awesome bro

add a if condition above the 3rd for loop like:

if hold > 0:

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;

}

That makes it very easy for me.

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

https://www.python.org/dev/peps/pep-3107/

Also this: https://stackoverflow.com/questions/14379753/what-does-mean-in-python-function-definitions

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.

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

This is far far more readable than prior solutions. I like it. SImilar to mine in c#

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