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

• Last Updated : 13 Mar, 2022

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:

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 ``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);``    ``int` `m = ``sizeof``(b) / ``sizeof``(b);` `    ``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

 ``

Output:

`4 8 16`

Time Complexity: O(max(n,m) * log(min(a, b)))

Auxiliary Space: O(1)

My Personal Notes arrow_drop_up