Between Two Sets Algorithm

In this article, I'll be describing how I solved the Between Two Sets Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

Problem 🎲

There will be two arrays of integers. Determine all integers that satisfy the following two conditions:

1. The elements of the first array are all factors of the integer being considered.
2. The integer being considered is a factor of all elements of the second array.

These numbers are referred to as being between the two arrays. Determine how many such numbers exist.

Example

Samle Input:

a = [2, 6]
b = [24, 36]

Samle Ouput:

There are two numbers between the arrays: 6 and 12. Return 2

Explanation

6%12 = 0, 6%6 = 0, 24%6 = 0 and 36%6 = 0 for the first value. 12%12 = 0, 12%6 = 0, 24%12 = 0 and 36%12 = 0 for the second value.

I'll get right into the algorithm. Please feel free to read the full question on HackerRank.

Solution 🔎

Step 1️⃣ : Figure out the range of values of the integer being considered. 🛣️

Looking at this problem, all that is required is to return the number of integers that satisfy the two conditions.

Let's call the given integer under consideration x

• Condition 1 states that the elements in the first array are all factors of x

  This means x should be equal to or greater than the largest element in the first array.

This is because any integer smaller than the largest element in this array can't possibly qualify as a factor. The elements themselves can be smaller since they are the factors of x.

• Condition 2 states that x is a factor of all elements in the second array.

  You can translate this condition to mean that the elements in the second array are all multiples of x. For this to be logical, x should be greater than or equal to the minimum number in the second array.

Now we've got a range of numbers to check for x. This is translated to:

for i in range(max(a), min(b)+1):

Step 2️⃣: Translate the two conditions using conditional statements. ⚙️

Before coding out the conditional statements, let's:

• Create a variable, result to count the number of integers that satisfy both conditions.
• Create a boolean isFactorMultiple to check if a given integer in the range satisfies both conditions.

result = 0
isFactorMultiple = True

Step 3️⃣: Loop through both the range of possible integers and both arrays while checking for both conditions.

We'll call the first array a and the second, b.

• For the first condition, if i % num != 0, it means the given element, ele in a is not a factor of x, and then we break out of this loop.

  for num in a:
    if i % num != 0:
        isFactorMultiple = False
            break
  

• For the second condition, if num % i != 0, it means the given element, ele is not a multiple of x, and then we break out of this loop.

  for num in a:
    if num % i != 0:
        isFactorMultiple = False
            break
  

• Finally, if a given element ele satisfies both conditions, it means isFactorMultiple = True, and we increment our counter, result by 1.
• And return result.

if isFactorMultiple == True:
            result += 1

Full code:

def getTotalX(a, b):
    # Write your code here
    result = 0

    for i in range(max(a), min(b)+1):
        isFactorMultiple = True
        for num in a:
            if i % num !=0:
                isFactorMultiple = False
                break

        for num in b:
            if num % i != 0:
                isFactorMultiple = False
                break

        if isFactorMultiple == True:
            result += 1
    return result


getTotalX([2, 4], [16, 32, 96])
>> 3

Explanation

• 2 and 4 divide evenly into 4, 8, 12 and 16.
• 4, 8 and 16 divide evenly into 16, 32, 96.
• 4, 8 and 16 are the only three numbers for which each element of a is a factor and each is a factor of all elements of b.

Hope this helps with understanding this challenge. Happy Coding!👨🏽‍💻