Integers X and K are given. The task is to find highest K-digit number divisible by X. Examples:
Input : X = 30, K = 3 Output : 990 990 is the largest three digit number divisible by 30. Input : X = 7, K = 2 Output : 98
An efficient solution is to use below formula.
ans = MAX - (MAX % X) where MAX is the largest K digit number which is 999...K-times
The formula works on simple school method division. We remove remainder to get the largest divisible number.
Python3
# Python code to find highest # K-digit number divisible by X def answer(X, K): # Computing MAX MAX = pow(10, K) - 1 #returning ans return (MAX - (MAX % X)) X = 30; K = 3; print(answer(X, K)); # Code contributes by Mohit Gupta_OMG <(0_o)> |
Output :
990
Time Complexity: O(logn)
Auxiliary Space: O(1)
Please refer complete article on Largest 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!
