[Hackerrank] – Between Two Sets Solution

2.1K

Question: You will be given two arrays of integers and asked to determine all integers between two sets that satisfy the following two conditions:
– The elements of the first array are all factors of the integer being considered
– The integer being considered is a factor of all elements of the second array

Input:
a = { 2, 6 }
b = { 24, 36 }

Output:
2

I really want to simplify this really confusing problem statement first.

The hardest part about this problem is to understand what is it actually saying. To put it in really simple words, you are provided with 2 arrays. Now you need to find a count of integers that satisfy the conditions:

• The integers should be multiples of each element of first array.
• The integers should be factors of each element of second array.

That is all you need to find out in the problem. Just return the count and your solution would have a successful submission.

For the above example, you can find 2 such integers. 6 and 12. You can verify that by:

First condition (multiple of each element of array 'a')
2 * 3 = 6
6 * 1 = 6
2 * 3 = 12
6 * 2 = 12

Second condition (factor of each element of array 'b')
24 % 6 = 0
24 % 12 = 0
36 % 6 = 0
36 % 12 = 0Code language: PHP (php)

So you could find 2 such integers between two sets, and hence that is the answer.

Brute Force Method:

A brute force method to solve this problem would be:

1. Find all the multiples of each element of first array.
2. Get all the factors of each element of second array.
3. Make an intersection of all the above integers.
4. Count the number of common integers you could find.

The only problem with this approach is that you spend a lot of time just to compute the multiples and finding the common elements. This would result in a very high time complexity. Surely, we need to find an optimized way.

Efficient Way:

You need to stop and think, why do you even need to find out all the multiples of array a. We are interested in integers that are a multiple of each of the element of array a. Thus, if we find the lowest common multiple, that can give us a starting point.

Similarly, we do not need all the factors of all the elements of array b. We are just interested in integers that are factors of every element. So, finding the greatest common divisor can give you a good starting point.

Next, we are sure that the integers are in the range of LCM (Lowest common multiple) and GCD (Greatest common divisor). The algorithm will be:

1. Find the LCM of all integers of array a.
2. Next, find the GCD of all integers of array b.
3. Count the number of multiples of LCM that are divisible by the GCD.

Code:

  int getGCD(int n1, int n2) {
    if (n2 == 0) {
      return n1;
    }
    return getGCD(n2, n1 % n2);
  }

  int getLCM(int n1, int n2) {
    if (n1 == 0 || n2 == 0)
      return 0;
    else {
      int gcd = getGCD(n1, n2);
      return Math.abs(n1 * n2) / gcd;
    }
  }

  public int getTotalX(List<Integer> a, List<Integer> b) {
    int result = 0;

    // Get LCM of all elements of a
    int lcm = a.get(0);
    for (Integer integer : a) {
      lcm = getLCM(lcm, integer);
    }

    // Get GCD of all elements of b
    int gcd = b.get(0);
    for (Integer integer : b) {
      gcd = getGCD(gcd, integer);
    }

    // Count multiples of lcm that divide the gcd
    int multiple = 0;
    while (multiple <= gcd) {
      multiple += lcm;

      if (gcd % multiple == 0)
        result++;
    }

    return result;
  }
Code language: Java (java)

Time Complexity: O(n \log n)
Space Complexity: O(\log n)
You can also find the code and testcases on Github as well.

Video Explanation: