Between two sets

HackerRank: Between Two Sets in Python

I found another really interesting problem on HackerRank called Between Two Sets. It is interesting because there was some math to be applied to the problem. The problem is a part of the implementation series on algorithms. The problem description is

Consider two sets of positive integers,  and . We say that a positive integer, x, is between sets A and B if the following conditions are satisfied:

  1. All elements in A are factors of x.
  2. x is a factor of all elements in B.

In other words, some x is between A and B if that value of x satisfies  for every  in A and also satisfies  for every  in B. For example, if  and  , then our possible x values are 6 and 12.

Given A and B, find and print the number of integers (i.e., possible x‘s) that are between the two sets.

There are some constraints given to the between two sets.  These constraints mean that it will be possible to make a bruteforce solution.  We could test every number between 1 and 100 to see if they satisfy the condition for all numbers in both A and B. However, we can also look at a little bit of math to find some properties of the numbers we are testing.

Greatest Common Divisor of set B

Rather than having to test each candidate number against all elements of set B, we can look at the greatest common divisor for set B.

The greatest common divisor tells us what the biggest number x is that is a factor of a and b such that and . This we can find for two numbers, and then find the greatest common divisor between this result and the next element of the set B. Doing this finds the greatest common divisor for the whole set B – let us denote that as gcd(B). Based on this, we know that the numbers we are looking for needs to divide this number cleanly. Since gcd(B) is a divisor for all numbers in B, then if the number is a divisor of gcd(B), then it is also a divisor of all numbers in B. Furthermore, we can infer that it needs to be equal to or less than this number.

The first problem we encountered the gcd algorithm was in problem 9 of  Project Euler and later on I tested different c# implementations of it. Always they have relied on Euclid’s algorithm and the solution I will implement in Python does the same. However due to the language constructs, it can be implemented really smoothly as

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

Least Common Multiplier of set A

Now we have reduced set B to a single number let us do the same for A. Since all elements of A needs to be a factor of the number we can apply the least common multiplier. The least common multiple (lcm) of a and b is the smallest number x that satisfies that both a and b are factors of x. Sounds exactly like what we are looking for right?

Once we have a gcd method implemented, it is really easy to implement lcm. It can be done as

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

I have chosen to use the // operator to make sure we return an integer rather than a float. We could also have converted it to int afterwards.

Solving Between Two Sets

Now we have a method for representing each set by one number. It is a lot easier to test between two numbers than between two sets. We also know that the number we are looking for is between lcm(A) and gcd(B). Furthermore, we know that the number has to be an integer multiple of lcm(A). Because otherwise the number wont be divisible by lcm(A).

So we can implement it in python as

def getTotalX(a, b):

    min_gcd = reduce(gcd, b)
    max_lcm = reduce(lcm, a)
    count = sum([1 for x in range(max_lcm, min_gcd+1, max_lcm) if min_gcd % x == 0])

    return count

line number 6 corresponds to a normal loop where I test all values of x. I just reduced it to one line, as that looks nice. The reduce method takes a function and a sequence, and then it applies the function to the first two elements. Takes the output and applies the function to that and the next element and so forth. Exactly what we described we needed in the gcd section.

Once we have that, then we can count all the multiples of gcd(A) that cleanly divides gcd(B) and get the answer. I still haven’t figured out how to time the solutions, but it is accepted by hackerrank without timing out.

Posted by Kristian

Leave a Reply