Given an array and a number k, the task is to find if LCM of the array is divisible by k or not.
Examples :
Input : int[] a = {10, 20, 15, 25}
k = 3
Output : true
Input : int[] a = {24, 21, 45, 57, 36};
k = 23;
Output : false
One simple solution is to first find LCM of array elements, then check if LCM is divisible by k or not.
Here, without calculating the LCM of the number we can find that LCM of the array of number is divisible by a prime number k or not. If any number of the array is divisible by prime number k, then the LCM of the number is also divisible by prime number k.
C++
// C++ program to find LCM of // array of number is divisible // by a prime number k or not #include<iostream> using namespace std; // Function to check any number of // array is divisible by k or not bool func(int a[], int k, int n) { // If any array element is divisible // by k, then LCM of whole array // should also be divisible. for (int i = 0; i < n; i++) if (a[i] % k == 0) return true; return false; } // Driver Code int main() { int a[] = {14, 27, 38, 76, 84}; int k = 19; bool res = func(a, k, 5); if(res) cout<<"true"; else cout<<"false"; return 0; } // This code is contributed // by Mr. Somesh Awasthi |
Java
// Java program to find LCM of // array of number is divisible // by a prime number k or not import java.lang.*; import java.util.*; class GFG { // Function to check any number // of array is divisible by k or not static boolean func( int a[], int k) { // If any array element is divisible // by k, then LCM of whole array // should also be divisible. for (int i = 0; i < a.length; i++) if (a[i] % k == 0) return true; return false; } // Driver Code public static void main(String args[]) { int[] a = {14, 27, 38, 76, 84}; int k = 19; boolean res = func(a, k); System.out.println(res); } } |
Python 3
# Python 3 program to find LCM # of array of number is divisible # by a prime number k or not # Function to check any number of # array is divisible by k or not def func( a, k, n) : # If any array element is # divisible by k, then LCM # of whole array should also # be divisible. for i in range(0, n) : if ( a[i] % k == 0): return True # Driver Code a = [14, 27, 38, 76, 84] k = 19res = func(a, k, 5) if(res) : print("true") else : print("false") # This code is contributed # by Nikita Tiwari. |
C#
// C# program to find LCM of array // of number is divisible by a prime // number k or not using System; class GFG { // Function to check any number of // array is divisible by k or not static bool func(int []a, int k) { // If any array element is // divisible by k, then LCM // of whole array should also // be divisible. for (int i = 0; i < a.Length; i++) if (a[i] % k == 0) return true; return false; } // Driver code public static void Main() { int []a = {14, 27, 38, 76, 84}; int k = 19; bool res = func(a, k); Console.Write(res); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find LCM of // array of number is divisible // by a prime number k or not // Function to check any number of // array is divisible by k or not function func( $a, $k, $n) { // If any array element is divisible // by k, then LCM of whole array // should also be divisible. for ($i = 0; $i < $n; $i++) if ($a[$i] % $k == 0) return true; return false; } // Driver Code $a = array(14, 27, 38, 76, 84); $k = 19; $res = func($a, $k, 5); if($res) echo"true"; elseecho"false"; // This code is contributed by nitin mittal ?> |
Javascript
<script> // javascript program to find LCM of // array of number is divisible // by a prime number k or not // Function to check any number // of array is divisible by k or not function func(a , k) { // If any array element is divisible // by k, then LCM of whole array // should also be divisible. for (let i = 0; i < a.length; i++) if (a[i] % k == 0) return true; return false; } // Driver Code let a = [ 14, 27, 38, 76, 84 ]; var k = 19; let res = func(a, k); document.write(res); // This code is contributed by todaysgaurav </script> |
Output :
true
Time Complexity: O(n)
Auxiliary Space: O(1)
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
