Between Two Sets, Algorithm problem

 

Consider two sets of positive integers, A= {a0,a1…an-1} andA= {b0,b1…bn-1} . We say that a positive integer, , is between sets and if the following conditions are satisfied:

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

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

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

Input Format

The first line contains two space-separated integers describing the respective values of (the number of elements in set ) and (the number of elements in set ).
The second line contains distinct space-separated integers describing .
The third line contains distinct space-separated integers describing .

Constraints

Output Format

Print the number of integers that are considered to be between and .

Sample Input

2 3
2 4
16 32 96

Sample Output

3

Explanation

There are three values between and :

  • :
    • All the elements in evenly divide .
    • evenly divides all the elements in .
  • :
    • All the elements in evenly divide .
    • evenly divides all the elements in .
  • :
    • All the elements in evenly divide .
    • evenly divides all the elements in .

Thus, we print as our answer.

 

Solution in PHP

problem link Click Here

If any problem, feel free to comment or contact.

 

 


<?php

$handle = fopen ("php://stdin","r");
fscanf($handle,"%d %d",$n,$m);
$a_temp = fgets($handle);
$a = explode(" ",$a_temp);
array_walk($a,'intval');
$b_temp = fgets($handle);
$b = explode(" ",$b_temp);
array_walk($b,'intval');

$lower_bound = $a[$n-1];
$upper_bound = $b[0];

$count_x = 0;

for($i = 1; $i <= $upper_bound; $i++){
$sum_mod = 0;

for($j = 0; $j < $n; $j++){
if ($i%$a[$j]!=0) {
$sum_mod=1;
}
}

for($k = 0; $k < $m; $k++){
if ($b[$k] % $i) {
$sum_mod =1;
}
}

if($sum_mod == 0){
$count_x++;
}
}

echo $count_x;

?>

 

I am PHP problem solver at Hackerrank. I am preparing myself for PHP zend certification exam with Masud Alam sir.
I have completed few websites using LARAVEL, also have experience on WORDPRESS.

Leave a Reply

Your email address will not be published. Required fields are marked *