Smallest number divisible by n and has at-least k trailing zeros
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 = 375 k = 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.