 # What is approach of subtract leading digit(SUBLD) problem?

How to solve this problem?

Use binary search to solve it, just for the number mid, count the number of steps for mid to reach 0.
Use a bit of maths to count steps for mid without using brute force. For mid = 1343, [(1343-1000)/ first digit of 1343] will give you the number of steps in very fewer iterations and the number reduces to 999 for the next iteration. Keep doing this till the number becomes 0.

1 Like

You can solve this question using binary search and how many number of step you need to remove that MSD
Ex.

N = abc
Then

Step for remove a is

bc/a

You need
f(N) = (bc)/a + f(N - (bc)/a )

And you will find max digit you have to find base condition for recursion

Thanks got it…

Thanks abba5 got it.

1 Like

One thing to notice is that for each increasing power of ten, you need to go through the “gate” of, for example, 1002 \to 1001 \to 1000 \to 999 to get down to the next fewer digits. There can be some variation within the n-digit numbers (for example 45 could arise from 49 or 50) but to get to n{+}1 digits, that sequence to power-of-ten and then all-nines through the number-of-digits change is obligatory.

So some precalculation makes sense, to avoid treading that path repeatedly. In fact what I did was work up from the power of ten to each leading digit change (by calculation), then also work back from the all-nines value, because that would require “targeting” when running the process backwards (ascending), so used forwards (descending) to get steps from that value.

So I ended up with a framework of 122 known values, the highest possible value for minimum steps to reach each new leading digit, which would then determine the best values for any k by stepping up from one of those with a fixed leading digit. Then for each input it was a lookup and calculation.