Hackerrank: Between Two Sets

gcd-and-lcm

This is the problem statement:

You will be given two arrays of integers and asked to 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. You
must determine how many such numbers exist.

I came across this while solving an 'easy' question in Hackerrank. Though it was easy to devise a brute force solution to this problem, I saw a very short solution in the discussions' section:

  1. Find the LCM of all the integers of array A.
  2. Find the GCD of all the integers of array B.
  3. Count the number of multiples of LCM that evenly divides the GCD.

This seems to work but I can't get my head around it. I want to understand that solution because it runs at a better time complexity. Could somebody please explain it?

Edit:

I know LCM and GCD. But I think I have lost all my intelligence in order to comprehend a simple solution in hand. I shall appreciate any intuition or instinct regarding this.

Best Answer

Let the LCM of the numbers in A be $L$ and the GCD of the numbers in $B$ be $G$. A number satisfying condition $1$ is a multiple of each number in $A$, so it's a multiple of $L$. Similarly, a number satisfying condition $2$ is a divisor of $G$, so the question is simply, "How many multiples of $L$ are divisors of $G$?"

Related Question