Integers X and K are given. The task is to find the smallest K-digit number divisible by X.
Examples :
Input : X = 83, K = 5 Output : 10043 10040 is the smallest 5 digit number that is multiple of 83. Input : X = 5, K = 2 Output : 10
A simple solution is to try all numbers starting from the smallest K digit number
(which is 100…(K-1)times) and return the first number divisible by X.
An efficient solution would be :
Compute MIN : smallest K-digit number (1000...(K-1)times) If, MIN % X is 0, ans = MIN else, ans = (MIN + X) - ((MIN + X) % X)) This is because there will be a number in range [MIN...MIN+X] divisible by X.
C++
// C++ code to find smallest K-digit number// divisible by X#include <bits/stdc++.h>using namespace std;// Function to compute the resultint answer(int X, int K){ // Computing MIN int MIN = pow(10, K - 1); // MIN is the result if (MIN % X == 0) return MIN; // returning ans return ((MIN + X) - ((MIN + X) % X));}// Driver Codeint main(){ // Number whose divisible is to be found int X = 83; // Max K-digit divisible is to be found int K = 5; cout << answer(X, K);} |
Java
// Java code to find smallest K-digit// number divisible by Ximport java.io.*;import java.lang.*;class GFG { public static double answer(double X, double K) { double i = 10; // Computing MIN double MIN = Math.pow(i, K - 1); // returning ans if (MIN % X == 0) return (MIN); else return ((MIN + X) - ((MIN + X) % X)); } public static void main(String[] args) { // Number whose divisible is to be found double X = 83; double K = 5; System.out.println((int)answer(X, K)); }}// Code contributed by Mohit Gupta_OMG <(0_o)> |
Python3
# Python code to find smallest K-digit # number divisible by Xdef answer(X, K): # Computing MAX MIN = pow(10, K-1) if(MIN % X == 0): return (MIN) else: return ((MIN + X) - ((MIN + X) % X)) X = 83; K = 5; print(answer(X, K)); # Code contributed by Mohit Gupta_OMG <(0_o)> |
C#
// C# code to find smallest K-digit// number divisible by Xusing System;class GFG { // Function to compute the result public static double answer(double X, double K) { double i = 10; // Computing MIN double MIN = Math.Pow(i, K - 1); // returning ans if (MIN % X == 0) return MIN; else return ((MIN + X) - ((MIN + X) % X)); } // Driver code public static void Main() { // Number whose divisible is to be found double X = 83; double K = 5; Console.WriteLine((int)answer(X, K)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP code to find smallest // K-digit number divisible by X// Function to compute // the resultfunction answer($X, $K){ // Computing MIN $MIN = pow(10, $K - 1); // MIN is the result if ($MIN % $X == 0) return $MIN; // returning ans return (($MIN + $X) - (($MIN + $X) % $X));}// Driver Code// Number whose divisible// is to be found$X = 83;// Max K-digit divisible// is to be found$K = 5;echo answer($X, $K);// This code is contributed by ajit?> |
Javascript
<script>// Javascript code to find smallest // K-digit number divisible by X// Function to compute // the resultfunction answer(X, K){ // Computing MIN let MIN = Math.pow(10, K - 1); // MIN is the result if (MIN % X == 0) return MIN; // returning ans return ((MIN + X) - ((MIN + X) % X));}// Driver Code// Number whose divisible// is to be foundlet X = 83;// Max K-digit divisible// is to be foundlet K = 5;document.write(answer(X, K)); // This code is contributed by sravan kumar</script> |
Output :
10043
Time Complexity: O(logk)
Auxiliary Space: O(1)
This article is contributed by Rohit Thapliyal. 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 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!
