Algorithm

Problem Name: Algorithms - Between Two Sets

In this HackerRank Functions in Algorithms - Java programming problem solution,

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

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

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

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

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

Constraints

• 1 <= n,m <= 10
• 1 <= a[i] <= 100
• 1 <= b[j] <= 100

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int lcm(int a, int b) { return a * b / gcd(a, b); }

int main() {
int n, m, a[10], b[10];
cin >> n >> m;
for (int i = 0; i  <  n; i++) {
cin >> a[i];
}
for (int i = 0; i  <  m; i++) {
cin >> b[i];
}
int lcmA = a[0];
for (int i = 1; i  <  n; i++) {
if (lcmA > 100) {
lcmA = 101;
break;
}
lcmA = lcm(lcmA, a[i]);
}
int gcdB = b[0];
for (int i = 1; i  <  m; i++) {
gcdB = gcd(gcdB, b[i]);
}
int cnt = 0;
for (int i = lcmA; i  < = gcdB; i += lcmA) {
bool flag = true;
for (int j = 0; j  <  m; j++) {
if (b[j] % i != 0) {
flag = false;
break;
}
}
if (flag) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}
``````
Copy The Code &

#2 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

/*
* Complete the getTotalX function below.
*/
static int getTotalX(int[] a, int[] b) {
boolean var,var2;int i;int j;int m = 0;
for(i = a[a.length-1]; i  < = b[0]; i++){
var = false;
for(j = 0; j <  a.length; j++){
if(i%a[j] == 0){
var = true;
}else{
var = false;
break;
}
}
if(var == true){
var2 = false;
for(int k = 0; k < b.length; k++){
if(b[k]%i == 0){
var2 = true;
}else{
var2 = false;
break;
}

}
if(var2 == true){
m++;
}
}
}
return m;
}

private static final Scanner scan = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nm = scan.nextLine().split(" ");

int n = Integer.parseInt(nm[0].trim());

int m = Integer.parseInt(nm[1].trim());

int[] a = new int[n];

String[] aItems = scan.nextLine().split(" ");

for (int aItr = 0; aItr  <  n; aItr++) {
int aItem = Integer.parseInt(aItems[aItr].trim());
a[aItr] = aItem;
}

int[] b = new int[m];

String[] bItems = scan.nextLine().split(" ");

for (int bItr = 0; bItr  <  m; bItr++) {
int bItem = Integer.parseInt(bItems[bItr].trim());
b[bItr] = bItem;
}

int total = getTotalX(a, b);

bw.write(String.valueOf(total));
bw.newLine();

bw.close(>;
}
}
``````
Copy The Code &

#3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Linq;

class Solution
{
static void Main(String[] args)
{
//No need to capture number of elments in set A and B as I use foreach loop to iterate them.
var setA = Array.ConvertAll(a_temp, Int32.Parse);
var setB = Array.ConvertAll(b_temp, Int32.Parse);
int total = getTotalX(setA, setB);
Console.WriteLine(total);
}

static int getTotalX(int[] a, int[] b)
{
var totalXs = 0;
var maximumA = a.Max(); //Time-complexity O(n)
var minimumB = b.Min(); //Time-complexity O(m)
var counter = 1;
var multipleOfMaxA = maximumA;

while (multipleOfMaxA  < = minimumB)
{
var factorOfAll = true;

foreach (var item in a) //Time complexity O(n)
{
if (multipleOfMaxA % item != 0)
{
factorOfAll = false;
break;
}
}

if (factorOfAll)
{
foreach (var item in b) //Time complexity O(m)
{
if (item % multipleOfMaxA != 0)
{
factorOfAll = false;
break;
}
}
}

if (factorOfAll)
totalXs++;

counter++;
multipleOfMaxA = maximumA * counter; //Here counter is the x factor which contributes to O(x(n+m)) complexity.
}
}
}
``````
Copy The Code &

#4 Code Example with Python Programming

```Code - Python Programming```

``````
import sys

def check_a(number, a):
for el in a:
if number % el != 0:
return False
return True

def check_b(number, b):
for el in b:
if el % number != 0:
return False
return True

def getTotalX(a, b):
res = 0
max_a = max(a)
min_b = min(b)

probe = max_a

while probe <= min_b:
if check_a(probe, a) and check_b(probe, b):
res += 1
probe += max_a

return res

if __name__ == "__main__":
n, m = input().strip().split(' ')
n, m = [int(n), int(m)]
a = list(map(int, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))
total = getTotalX(a, b)
print(total)
``````
Copy The Code &

#5 Code Example with PHP Programming

```Code - PHP Programming```

``````

``````
Copy The Code &