Given the margin of integers 0-9, what is the last number that I can write before any integer ends?

Question

As the name says, given the stock of integers 0–9, what is the last number I can write before any integer ends?

So, if they give me a margin, say 10 for each number from 0 to 9, then what is the last number I can write before any number ends. For example, with a margin of 2, I can write numbers 1 ... 10:

1 2 3 4 5 6 7 8 9 10

at this moment, my margin for them is 0, and I can’t write 11. Also note that if I was given a margin of 3, I could still only write the numbers 1 ... 10, because 11 would cost me 2 units that would leave my margin for units at -1.

What I have come up with so far:

public class Numbers { public static int numbers(int stock) { int[] t = new int[10]; for (int k = 1; ; k++) { int x = k; while (x > 0) { if (t[x % 10] == stock) return k-1; t[x % 10]++; x /= 10; } } } public static void main(String[] args) { System.out.println(numbers(4)); } } 

With this, I can get the right answer for fairly large stock sizes. With a margin of 10 ^ 6, the code ends in ~ 2 seconds, and with a margin of 10 ^ 7 numbers, it takes as much as 27 seconds. This is not very good, as I am looking for a solution that can handle sizes up to 10 ^ 16, so I probably need an O (log (n)) solution.

This is homework, so I have not come here without a fight against this pickling for quite some time. I could not come up with anything similar to googling, and tungsten alpha does not recognize any pattern that this gives.

What I have done so far is that all of them will all end. I have no evidence, but it is.

Can anyone come up with some advice? Thank you very much.

---

EDIT:

I came up with and implemented an effective way to find the value of the numbers 1 ... n thanks to btilly pointers (see his post and comments below, also marked as a solution). I will talk about this later after I implemented a binary search to find the last number that you can record with this stock later today.

---

EDIT 2: Solution

I completely forgot about this post, so my apologies for not editing in my decision earlier. However, I will not copy the actual implementation.

My room rate code does the following:

First, choose a number, for example. 9999. Now we get the value by summing the cost of each dozen digits like this:

 9 9 9 9 ^ ^ ^ ^ ^ ^ ^ roof(9999 / 10^1) * 10^0 = 1000 ^ ^ roof(9999 / 10^2) * 10^1 = 1000 ^ roof(9999 / 10^3) * 10^2 = 1000 roof(9999 / 10^4) * 10^3 = 1000 

Thus, the cost of 9999 is 4000.

same for 256:

 2 5 6 ^ ^ ^ ^ ^ roof(256 / 10^1) * 10^0 = 26 ^ roof(256 / 10^2) * 10^1 = 30 roof(256 / 10^3) * 10^2 = 100 

Thus, the cost of 256 is 156.

Implementation with this idea will make the program work only with numbers that do not have the digits 1 or 0, so further logic is needed. Let me call the method described above C (n, d) , where n is the number for which we get the value, and d is d 'this digit from n , which we are currently working with. Let it also determine the method D (n, d) , which will return d 'th digit from n . Then we apply the following logic:

 sum = C(n, d) if D(n, d) is 1: for each k < d, k >= 0 : sum -= ( 9 - D(n, k) ) * 10^(k-1); else if D(n, d) is 0: sum -= 10^(d-1) 

In this case, the program will calculate the correct cost for the number. After that, we simply use binary search to find the number with the correct value.

Answer 1

Step 1. Write an effective function to calculate how much stock you need to use to record all numbers up to N (Hint: compute everything that was used to write the numbers in the last digit using a formula, and then use recursion to calculate everything that was used in the other digits.)

Step 2. Do a binary search to find the last number that you can record with your margin.

Answer 2

We can calculate the answer directly. A recursive formula can determine how many stocks you need to get from 1 to numbers that have values ​​of ten minus 1:

 f(n, power, target){ if (power == target) return 10 * n + power; else return f(10 * n + power, power * 10, target); } f(0,1,1) = 1 // a stock of 1 is needed for the numbers from 1 to 9 f(0,1,10) = 20 // a stock of 20 is needed for the numbers from 1 to 99 f(0,1,100) = 300 // a stock of 300 is needed for the numbers from 1 to 999 f(0,1,1000) = 4000 // a stock of 4000 is needed for the numbers from 1 to 9999 

Where it becomes more complicated, an additional 1 taken into account, which is necessary when our calculation is typed after the first multiple of any of the above coefficients; for example, on the second multiple of 10 (11-19) we need an additional 1 for each number.

JavaScript Code:

 function f(stock){ var cs = [0]; var p = 1; function makeCoefficients(n,i){ n = 10*n + p; if (n > stock){ return; } else { cs.push(n); p *= 10; makeCoefficients(n,i*10); } } makeCoefficients(0,1); var result = -1; var numSndMul = 0; var c; while (stock > 0){ if (cs.length == 0){ return result; } c = cs.pop(); var mul = c + p * numSndMul; if (stock >= mul){ stock -= mul; result += p; numSndMul++; if (stock == 0){ return result; } } var sndMul = c + p * numSndMul; if (stock >= sndMul){ stock -= sndMul; result += p; numSndMul--; if (stock == 0){ return result; } var numMul = Math.floor(stock / mul); stock -= numMul * mul; result += numMul * p; } p = Math.floor(p/10); } return result; } 

Output:

 console.log(f(600)); 1180 console.log(f(17654321)); 16031415 console.log(f(2147483647)); 1633388154