Given a number n, find the LCM of its digits.
Examples:
Input : 397 Output : 63 LCM of 3, 9 and 7 is 63. Input : 244 Output : 4 LCM of 2, 4 and 4 is 4.
Method 1:
Follow the steps to solve this problem:
- Initialise a variable l = 1
- While n is greater than 0. Do the following:
- Find the LCM of n % 10 and lcm
- Check if lcm == 0 , return 0
- Initialise n = n / 10;
- Finally, return l.
Follow the steps below to implement the above approach:
C++
// CPP program to find LCM of digits of a number#include <bits/stdc++.h>using namespace std;// Recursive function to return gcd of a and blong long gcd(long long int a, long long int b){ if (b == 0) return a; return gcd(b, a % b);}// Function to return LCM of two numberslong long lcm(int a, int b) { return (a / gcd(a, b)) * b; }int digitLCM(int n){ int l = 1; while (n > 0) { l = lcm(n % 10, l); // If at any point LCM become 0. // return it if (lcm == 0) return 0; n = n / 10; } return l;}// driver codeint main(){ long n = 397; cout << digitLCM(n); return 0;} |
Java
// Java program to find LCM of digits of a numberimport java.io.*;class GFG{// define lcm functionstatic int lcm_fun(int a, int b){ if (b == 0) return a; return lcm_fun(b, a % b);}static int digitLCM(int n){ int lcm = 1; while (n > 0) { lcm = (n % 10 * lcm) / lcm_fun(n % 10, lcm); // If at any point LCM become 0. // return it if (lcm == 0) return 0; n = n/10; } return lcm;}// driver codepublic static void main(String[] args){ int n = 397; System.out.println(digitLCM(n));}}// This code is contributed by mits |
Python3
# Python3 program to find# LCM of digits of a number# define lcm functiondef lcm_fun(a, b): if (b == 0): return a; return lcm_fun(b, a % b);def digitLCM(n): lcm = 1; while (n > 0): lcm = int((n % 10 * lcm) / lcm_fun(n % 10, lcm)); # If at any point LCM # become 0. return it if (lcm == 0): return 0; n = int(n / 10); return lcm;# Driver coden = 397;print(digitLCM(n));# This code is contributed by mits |
C#
// C# program to find LCM of digits// of a numberclass GFG{ // define lcm functionstatic int lcm_fun(int a, int b){ if (b == 0) return a; return lcm_fun(b, a % b);}static int digitLCM(int n){ int lcm = 1; while (n > 0) { lcm = (n % 10 * lcm) / lcm_fun(n % 10, lcm); // If at any point LCM become 0. // return it if (lcm == 0) return 0; n = n/10; } return lcm;}// Driver Codepublic static void Main(){ int n = 397; System.Console.WriteLine(digitLCM(n));}}// This code is contributed by mits |
PHP
<?php// PHP program to find// LCM of digits of a number// define lcm functionfunction lcm_fun($a, $b){ if ($b == 0) return $a; return lcm_fun($b, $a % $b);}function digitLCM($n){ $lcm = 1; while ($n > 0) { $lcm = (int)(($n % 10 * $lcm) / lcm_fun($n % 10, $lcm)); // If at any point LCM // become 0. return it if ($lcm == 0) return 0; $n = (int)($n / 10); } return $lcm;}// Driver code$n = 397;echo digitLCM($n);// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find LCM of digits of a number // define lcm function function lcm_fun( a, b) { if (b == 0) return a; return lcm_fun(b, a % b); } function digitLCM( n) { let lcm = 1; while (n > 0) { lcm = (n % 10 * lcm) / lcm_fun(n % 10, lcm); // If at any point LCM become 0. // return it if (lcm == 0) return 0; n = parseInt(n / 10); } return lcm; } // Driver code let n = 397; document.write(digitLCM(n));// This code is contributed by gauravrajput1 </script> |
Output
63
Time Complexity: O(log n), the time complexity of this algorithm is O(log n) as we are making a single iteration and each iteration is taking O(1) time for computation.
Auxiliary Space: O(1), the space complexity of this algorithm is O(1) as we are using a single variable l to store the lcm of the digits.
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if 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!
