Integers X and K are given. The task is to find 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
An efficient solution would be :
Compute MIN : smallest K-digit number (1000...K-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.
Python3
# Python code to find smallest K-digit # number divisible by X def 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)> |
Output :
10043
Time Complexity: O(logk)
Auxiliary Space: O(1)
Please refer complete article on Smallest K digit number divisible by X for more details!
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!
