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

  • P1zzAdr0hn3 + 2 comments
    #!/bin/python3

import sys


n,m = input().strip().split(' ')
n,m = [int(n),int(m)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]
b = [int(b_temp) for b_temp in input().strip().split(' ')]
a.sort()
b.sort()
ausgabe = 0
for q in range(b[0] +1):
    if q >= a[-1]:
        for t in range(n):
            if q % a[t] != 0:
                break
            if t == n -1:
                for g in range(m):
                    if b[g] % q != 0:
                        break
                    if g == m -1:
                        ausgabe += 1
      
print(ausgabe)
    • 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.

    • skdubey + 0 comments

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