Two integers n and k are given. Our task is to print K-rounding of n. K-rounding is the minimum positive integer X, such that x ends with k or more zeros and is divisible by n.
Examples :
Input : n = 30, k = 3. Output : 3000 3000 is the smallest number that has at-least k 0s and is divisible by n. Input : n = 375, k = 4. Output : 30000
Method 1 :
The brute force approach is to start with result = 10k. Check if result is divided by n. If yes, it’s the answer, else increase it by 10k
Method 2 : The efficient approach is to calculate the LCM of 10k and n.
Suppose, n = 375, k = 4.
result = 10000.
Now, LCM of 375 and 10000 is the lowest number divided by both of them.
It will contain k or more zeros (because it is multiple of 10k) and will be a multiple of n as well.
Below is the implementation :
C++
// CPP code to print K-rounded value of n #include <bits/stdc++.h> using namespace std; // Function to compute the rounded value long long getRounding(long long n, long long k) { long long rounding = pow(10, k); // Computing GCD long long result = __gcd(rounding, n); // Returning LCM (GCD * LCM = n * k) return ((rounding * n) / result); } // Driver Code int main() { long long n = 375, k = 4; // Function call cout << getRounding(n, k); return 0; } |
Java
// JAVA Code For Smallest number divisible by // n and has at-least k trailing zeros import java.util.*; class GFG { // Function to find gcd static long gcd(long a, long b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } // Function to compute the rounded value public static long getRounding(long n, long k) { long rounding = (long)Math.pow(10, k); // Computing GCD long result = gcd(rounding, n); // Returning LCM (GCD * LCM = n * k) return ((rounding * n) / result); } /* Driver program to test above function */ public static void main(String[] args) { long n = 375, k = 4; // Function call System.out.println( getRounding(n, k)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# python Code For Smallest number # divisible by n and has # at-least k trailing zeros # Function to find gcd def gcd(a, b): # Everything divides 0 if (a == 0 or b == 0): return 0 # base case if (a == b): return a # a is greater if (a > b): return gcd(a - b, b) return gcd(a, b - a) # Function to compute the # rounded value def getRounding(n, k): rounding = pow(10, k); # Computing GCD result = gcd(rounding, n) # Returning LCM (GCD * LCM # = n * k) return ((rounding * n) / result) # Driver Code n = 375k = 4 # Function call print( int(getRounding(n, k))) # This code is contributed by Sam007 |
C#
// C# Code For Smallest number // divisible by n and has // at-least k trailing zeros using System; class GFG { // Function to find gcd static long gcd(long a, long b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Function to compute the rounded value public static long getRounding(long n, long k) { long rounding = (long)Math.Pow(10, k); // Computing GCD long result = gcd(rounding, n); // Returning LCM (GCD * LCM = n * k) return ((rounding * n) / result); } // Driver Code public static void Main() { long n = 375, k = 4; // Function call Console.Write( getRounding(n, k)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP Code For Smallest number // divisible by n and has // at-least k trailing zeros function gcd($a, $b) { // Everything divides 0 if ($a == 0 || $b == 0) return 0; // base case if ($a == $b) return $a; // a is greater if ($a > $b) return gcd($a - $b, $b); return gcd($a, $b - $a); } // Function to compute // the rounded value function getRounding($n, $k) { $rounding = intval(pow(10, $k)); // Computing GCD $result = gcd($rounding, $n); // Returning LCM (GCD * LCM = n * k) return intval(($rounding * $n) / $result); } // Driver code $n = 375; $k = 4; // Function call echo getRounding($n, $k); // This code is contributed by Sam007 ?> |
Javascript
<script> // javascript Code For Smallest number divisible by // n and has at-least k trailing zeros // Function to find gcd function gcd(a , b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Function to compute the rounded value function getRounding(n , k) { var rounding = Math.pow(10, k); // Computing GCD var result = gcd(rounding, n); // Returning LCM (GCD * LCM = n * k) return ((rounding * n) / result); } /* Driver program to test above function */ var n = 375, k = 4; // Function call document.write(getRounding(n, k)); // This code is contributed by todaysgaurav </script> |
Output :
30000
Time Complexity: O(logk + log(max(10k, n)), where n and k are the given integers.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
