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

help
, ,
1

How to solve this problem?
Link: https://www.codechef.com/MOSCWJ19/problems/SUBLD

2

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
3

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

4

Thanks got it…

5

Thanks abba5 got it.

1 Like
6

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.

Link to my Python code

7

You don’t need a binary search, just a cumulative double loop working upwards from the initial value 9.

It is the leading digit which controls how many we increase at a time.

Loop for powers of 10 (n), and then for leading digits (i), in blocks from i * 10^n to (i+1) * 10^n - 1

Within the inner loop, given the last digit of the preceding block, the starting last digit is (last digit + new leading digit - 10). Evaluate the last digit in the block as the largest number not exceeding 8 such that it is a multiple of i from the first. From there calculate the number of values within this block. A special case is in blocks starting with a 9, where the number that is all 9s is needed so that we can proceed from there to the next power of 10.

You can see my solution in C at https://www.codechef.com/viewsolution/21715024