Least Common Multiplier

HackerRank: Between Two Sets in Python

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. Continue reading →

Posted by Kristian in HackerRank, 4 comments