# Find numbers which are multiples of first array and factors of second array

Given two arrays **A[]** and **B[]**, the task is to find the integers which are divisible by all the elements of array **A[]** and divide all the elements of array **B[]**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:A[] = {1, 2, 2, 4}, B[] = {16, 32, 64}Output:4 8 16

4, 8 and 16 are the only numbers that

are multiples of all the elements of array A[]

and divide all the elements of array B[]

Input:A[] = {2, 3, 6}, B[] = {42, 84}Output:6 42

**Approach:** If **X** is a multiple of all the elements of the first array then **X** must be a multiple of the LCM of all the elements of the first array.

Similarly, If **X** is a factor of all the elements of the second array then it must be a factor of the GCD of all the elements of the second array and such **X** will exist only if GCD of the second array is divisible by the LCM of the first array.

If it is divisible then **X** can be any value from the range **[LCM, GCD]** which is a multiple of LCM and evenly divides GCD.

Below is the implementation of above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return the LCM of two numbers` `int` `lcm(` `int` `x, ` `int` `y)` `{` ` ` `int` `temp = (x * y) / __gcd(x, y);` ` ` `return` `temp;` `}` `// Function to print the required numbers` `void` `findNumbers(` `int` `a[], ` `int` `n, ` `int` `b[], ` `int` `m)` `{` ` ` `// To store the lcm of array a[] elements` ` ` `// and the gcd of array b[] elements` ` ` `int` `lcmA = 1, gcdB = 0;` ` ` `// Finding LCM of first array` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `lcmA = lcm(lcmA, a[i]);` ` ` `// Finding GCD of second array` ` ` `for` `(` `int` `i = 0; i < m; i++)` ` ` `gcdB = __gcd(gcdB, b[i]);` ` ` `// No such element exists` ` ` `if` `(gcdB % lcmA != 0) {` ` ` `cout << ` `"-1"` `;` ` ` `return` `;` ` ` `}` ` ` `// All the multiples of lcmA which are` ` ` `// less than or equal to gcdB and evenly` ` ` `// divide gcdB will satisfy the conditions` ` ` `int` `num = lcmA;` ` ` `while` `(num <= gcdB) {` ` ` `if` `(gcdB % num == 0)` ` ` `cout << num << ` `" "` `;` ` ` `num += lcmA;` ` ` `}` `}` `// Driver code` `int` `main()` `{` ` ` `int` `a[] = { 1, 2, 2, 4 };` ` ` `int` `b[] = { 16, 32, 64 };` ` ` `int` `n = ` `sizeof` `(a) / ` `sizeof` `(a[0]);` ` ` `int` `m = ` `sizeof` `(b) / ` `sizeof` `(b[0]);` ` ` `findNumbers(a, n, b, m);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `import` `java.util.*;` `class` `GFG` `{` `static` `int` `__gcd(` `int` `a, ` `int` `b)` `{` ` ` `if` `(b == ` `0` `)` ` ` `return` `a;` ` ` `return` `__gcd(b, a % b);` ` ` `}` `// Function to return the LCM of two numbers` `static` `int` `lcm(` `int` `x, ` `int` `y)` `{` ` ` `int` `temp = (x * y) / __gcd(x, y);` ` ` `return` `temp;` `}` `// Function to print the required numbers` `static` `void` `findNumbers(` `int` `a[], ` `int` `n,` ` ` `int` `b[], ` `int` `m)` `{` ` ` `// To store the lcm of array a[] elements` ` ` `// and the gcd of array b[] elements` ` ` `int` `lcmA = ` `1` `, gcdB = ` `0` `;` ` ` `// Finding LCM of first array` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `lcmA = lcm(lcmA, a[i]);` ` ` `// Finding GCD of second array` ` ` `for` `(` `int` `i = ` `0` `; i < m; i++)` ` ` `gcdB = __gcd(gcdB, b[i]);` ` ` `// No such element exists` ` ` `if` `(gcdB % lcmA != ` `0` `)` ` ` `{` ` ` `System.out.print(` `"-1"` `);` ` ` `return` `;` ` ` `}` ` ` `// All the multiples of lcmA which are` ` ` `// less than or equal to gcdB and evenly` ` ` `// divide gcdB will satisfy the conditions` ` ` `int` `num = lcmA;` ` ` `while` `(num <= gcdB)` ` ` `{` ` ` `if` `(gcdB % num == ` `0` `)` ` ` `System.out.print(num + ` `" "` `);` ` ` `num += lcmA;` ` ` `}` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `a[] = { ` `1` `, ` `2` `, ` `2` `, ` `4` `};` ` ` `int` `b[] = { ` `16` `, ` `32` `, ` `64` `};` ` ` `int` `n = a.length;` ` ` `int` `m = b.length;` ` ` `findNumbers(a, n, b, m);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Python3

`# Python3 implementation of the approach` `from` `math ` `import` `gcd` `# Function to return the LCM of two numbers` `def` `lcm( x, y) :` ` ` ` ` `temp ` `=` `(x ` `*` `y) ` `/` `/` `gcd(x, y);` ` ` `return` `temp;` `# Function to print the required numbers` `def` `findNumbers(a, n, b, m) :` ` ` `# To store the lcm of array a[] elements` ` ` `# and the gcd of array b[] elements` ` ` `lcmA ` `=` `1` `; __gcdB ` `=` `0` `;` ` ` `# Finding LCM of first array` ` ` `for` `i ` `in` `range` `(n) :` ` ` `lcmA ` `=` `lcm(lcmA, a[i]);` ` ` `# Finding GCD of second array` ` ` `for` `i ` `in` `range` `(m) :` ` ` `__gcdB ` `=` `gcd(__gcdB, b[i]);` ` ` `# No such element exists` ` ` `if` `(__gcdB ` `%` `lcmA !` `=` `0` `) :` ` ` `print` `(` `"-1"` `);` ` ` `return` `;` ` ` `# All the multiples of lcmA which are` ` ` `# less than or equal to gcdB and evenly` ` ` `# divide gcdB will satisfy the conditions` ` ` `num ` `=` `lcmA;` ` ` `while` `(num <` `=` `__gcdB) :` ` ` `if` `(__gcdB ` `%` `num ` `=` `=` `0` `) :` ` ` `print` `(num, end ` `=` `" "` `);` ` ` ` ` `num ` `+` `=` `lcmA;` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `a ` `=` `[ ` `1` `, ` `2` `, ` `2` `, ` `4` `];` ` ` `b ` `=` `[ ` `16` `, ` `32` `, ` `64` `];` ` ` ` ` `n ` `=` `len` `(a);` ` ` `m ` `=` `len` `(b);` ` ` ` ` `findNumbers(a, n, b, m);` ` ` `# This code is contributed by AnkitRai01` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` `static` `int` `__gcd(` `int` `a, ` `int` `b)` `{` ` ` `if` `(b == 0)` ` ` `return` `a;` ` ` `return` `__gcd(b, a % b);` `}` `// Function to return the LCM of two numbers` `static` `int` `lcm(` `int` `x, ` `int` `y)` `{` ` ` `int` `temp = (x * y) / __gcd(x, y);` ` ` `return` `temp;` `}` `// Function to print the required numbers` `static` `void` `findNumbers(` `int` `[]a, ` `int` `n,` ` ` `int` `[]b, ` `int` `m)` `{` ` ` `// To store the lcm of array a[] elements` ` ` `// and the gcd of array b[] elements` ` ` `int` `lcmA = 1, gcdB = 0;` ` ` `// Finding LCM of first array` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `lcmA = lcm(lcmA, a[i]);` ` ` `// Finding GCD of second array` ` ` `for` `(` `int` `i = 0; i < m; i++)` ` ` `gcdB = __gcd(gcdB, b[i]);` ` ` `// No such element exists` ` ` `if` `(gcdB % lcmA != 0)` ` ` `{` ` ` `Console.Write(` `"-1"` `);` ` ` `return` `;` ` ` `}` ` ` `// All the multiples of lcmA which are` ` ` `// less than or equal to gcdB and evenly` ` ` `// divide gcdB will satisfy the conditions` ` ` `int` `num = lcmA;` ` ` `while` `(num <= gcdB)` ` ` `{` ` ` `if` `(gcdB % num == 0)` ` ` `Console.Write(num + ` `" "` `);` ` ` `num += lcmA;` ` ` `}` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `[]a = { 1, 2, 2, 4 };` ` ` `int` `[]b = { 16, 32, 64 };` ` ` `int` `n = a.Length;` ` ` `int` `m = b.Length;` ` ` `findNumbers(a, n, b, m);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript implementation of the approach` `// Function to find nth centered` `// tridecagonal number` `function` `__gcd(a, b)` `{` ` ` `if` `(b == 0)` ` ` `return` `a;` ` ` ` ` `return` `__gcd(b, a % b);` ` ` `}` `// Function to return the LCM of two numbers` `function` `lcm(x, y)` `{` ` ` `var` `temp = (x * y) / __gcd(x, y);` ` ` `return` `temp;` `}` `// Function to print the required numbers` `function` `findNumbers(a, n, b, m)` `{` ` ` ` ` `// To store the lcm of array a[] elements` ` ` `// and the gcd of array b[] elements` ` ` `var` `lcmA = 1, gcdB = 0;` ` ` `// Finding LCM of first array` ` ` `for` `(` `var` `i = 0; i < n; i++)` ` ` `lcmA = lcm(lcmA, a[i]);` ` ` `// Finding GCD of second array` ` ` `for` `(` `var` `i = 0; i < m; i++)` ` ` `gcdB = __gcd(gcdB, b[i]);` ` ` `// No such element exists` ` ` `if` `(gcdB % lcmA != 0)` ` ` `{` ` ` `document.write(` `"-1"` `);` ` ` `return` `;` ` ` `}` ` ` `// All the multiples of lcmA which are` ` ` `// less than or equal to gcdB and evenly` ` ` `// divide gcdB will satisfy the conditions` ` ` `var` `num = lcmA;` ` ` `while` `(num <= gcdB)` ` ` `{` ` ` `if` `(gcdB % num == 0)` ` ` `document.write(num + ` `" "` `);` ` ` ` ` `num += lcmA;` ` ` `}` `}` `// Driver code` `var` `a = [ 1, 2, 2, 4 ];` `var` `b = [ 16, 32, 64 ];` `var` `n = a.length;` `var` `m = b.length;` `findNumbers(a, n, b, m);` `// This code is contributed by Ankita saini` `</script>` |

**Output:**

4 8 16