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

Between Two Sets

  • NicolasBi + 10 comments

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

    #!/bin/python3

import sys
from functools import reduce


def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)


def lcm_list(lst: list) -> int:
    return reduce(lcm, lst)


def gcd(a: int, b: int) -> int:
    while a % b != 0:
        a, b = b, (a % b)
    return b


def gcd_list(lst: list) -> int:
    return reduce(gcd, lst)


def evenly_divides(number: int, divisor: int) -> bool:
    return (number % divisor) == 0


def get_input():
    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()]
    return n, m, a, b


def main():
    n, m, a, b = get_input()
    
    # Find LCM of all integers of a
    lcm_value = lcm_list(a)
    
    # Find GCD of all integers of b
    gcd_value = gcd_list(b)
    
    # Count the number of multiples of LCM that evenly divides the GCD.
    counter = 0
    multiple_of_lcm = lcm_value
    while multiple_of_lcm <= gcd_value:
        if evenly_divides(gcd_value, multiple_of_lcm):
            counter += 1
        multiple_of_lcm += lcm_value

    print(counter)

    
if __name__ == "__main__":
    main()
    • stregz + 1 comment

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

      #!/bin/python

import sys
from fractions import gcd

n,m = raw_input().strip().split(' ')
n,m = [int(n),int(m)]
A = map(int,raw_input().strip().split(' '))
B = map(int,raw_input().strip().split(' '))

def LCM(a, b):
    return (a*b)//gcd(a,b)

lcm = reduce(LCM, A, 1)
gcd = reduce(gcd, B)

lcm_copy = lcm

count = 0
while lcm <= gcd:
    if(gcd % lcm) == 0:
        count += 1
    lcm = lcm + lcm_copy

print(count)
      • askarovdaulet + 5 comments

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

        import sys
from functools import reduce
from fractions import gcd

input()
a = map(int,input().strip().split())
b = map(int,input().strip().split())
lcm_a = reduce(lambda x,y: x*y//gcd(x,y), a)
gcd_b = reduce(gcd, b)
print(sum(1 for x in range(lcm_a,gcd_b+1,lcm_a) if gcd_b%x==0))
        • amelnychukoseen + 0 comments

          Damn this is nice.

        • mushthofa + 0 comments

          Nice

        • kanabos + 1 comment

          Not a big change but you can iterate less times:

          import sys
from functools import reduce
from fractions import gcd

input()
a = map(int,input().strip().split())
b = map(int,input().strip().split())
lcm_a = reduce(lambda x,y: x*y//gcd(x,y), a)
gcd_b = reduce(gcd, b)
gcd_b_copy = gcd_b
print(sum(1 for x in range(lcm_a,gcd_b+gcd_b_copy,lcm_a) if gcd_b%x==0))
          • xiaoliji + 1 comment

            1 is redundant. just 

            print(sum(gcd_b%x==0 for x in range(lcm_a,gcd_b+gcd_b_copy,lcm_a)))
        • it_beast + 0 comments

          Awesome

        • ssbreckenridge + 0 comments

          Note for python3.7:

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

    • 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 + 6 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!!

          • Rishi_Kumar_Soni + 0 comments

            can yo tell me the use of all

        • 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

    • __grj + 0 comments
      [deleted]
    • SebastianNielsen + 1 comment

      What is this syntax? 

      def gcd(a: int, b: int) -> int:

      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.

      • What is it for?
      • aymanabuelela + 0 comments

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

    • [deleted] + 5 comments

      Here is smaller code bro,

      def getTotalX(a, b):
    total = 0
    for x in list(range(a[-1], b[0] + 1)):
        hold = 0
        for v in a:
            if (x % v == 0): hold += 1
            else: hold = 0; break    
        
        for c in b:
            if (c % x == 0): hold += 1
            else: hold = 0; break       
        if (hold == len(a) + len(b)):
            total += 1   
    return total
      • anurag12345 + 0 comments

        Awesome bro

      • chandrakanthshy + 0 comments

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

        if hold > 0:

         for c in b:
 ....
 ....
      • gkjha009 + 0 comments

        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;

        let allElementsAreMultiple = false;
let numberIsMultipleOfAll  = false;

while(number <= minB){
    console.log('aMax ', maxA,'bMin ', minB, 'number ', number);
    // Every element of array  must be a multiple of considerd number
    allElementsAreMultiple = a.every(ele => number%ele === 0 );
    numberIsMultipleOfAll  = b.every(ele => ele%number === 0 );
    if( allElementsAreMultiple && numberIsMultipleOfAll )
        total++;
    number++;
}

return total;

        }

        That makes it very easy for me.

      • marcomereu2015 + 0 comments

        Thank you!

      • zaramaths123 + 0 comments

        i don't get why we use this line? if (hold == len(a) + len(b)):

    • jamesallenvinoy + 1 comment

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

      • AffineStructure + 1 comment

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

        • AffineStructure + 0 comments

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

    • amitkumar10591 + 0 comments

      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.

    • suryabteja + 0 comments

      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

    • martin89 + 0 comments

      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);
    • nalin39 + 0 comments

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