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:
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> |
4 8 16
Time Complexity: O(max(n,m) * log(min(a, b)))
Auxiliary Space: O(1)
Contact Us