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.
Loading...
  1. Practice
  2. Algorithms
  3. Implementation
  4. Between Two Sets
  5. Discussions

Between Two Sets

  • AffineStructure + 2 comments

    3 for loops = O(n^3)

    • P1zzAdr0hn3 + 5 comments

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

      #!/bin/python3

import sys

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
    
print(ausgabe)
      • namanrocks94 + 1 comment

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

        • P1zzAdr0hn3 + 1 comment

          i think its O(2n^2)

          • SalmanBhai + 1 comment

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

            • P1zzAdr0hn3 + 1 comment

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

              • paul_schmeida + 1 comment

                It's asymptotic actually :)

                • P1zzAdr0hn3 + 0 comments

                  :D I knew it was something like that.

      • suryach750 + 0 comments

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

      • MatricksDecoder + 1 comment

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

        • zad23 + 0 comments

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

      • ash_jo4444 + 0 comments

        Awesome solution !!

      • washimdas2013 + 0 comments

        Superb Dude!!

    • isabella_xy_sun + 2 comments

      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!

      #!/bin/python
import sys
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
print final
      • AffineStructure + 1 comment

        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

        • P1zzAdr0hn3 + 1 comment

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

          • AffineStructure + 1 comment

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

            • P1zzAdr0hn3 + 0 comments

              ... you're right^^

      • chinmay_zare + 0 comments

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