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.

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

## Between Two Sets

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

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