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.
n,m = map(int, input().strip().split(' '))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ausgabe = 0
for q in range(max(a), min(b) +1):
if all(q % arr == 0 for arr in a) and all(brr % q == 0 for brr in b):
ausgabe += 1
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:
4 8 12
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 !!
can yo tell me the use of all
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!
n,m = map(int,raw_input().strip().split(' '))
a = map(int,raw_input().strip().split(' '))
b = map(int,raw_input().strip().split(' '))
final = 0
lower,upper = max(a),min(b)
for i in xrange(lower,upper+1):
if sum(1 for k in a if i%k == 0) == n and sum(1 for k in b if k%i == 0) == m:
final += 1
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
With time complexity we drop out the constant term.
"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.