Given a stock of integers 0-9, what is the last number I can write before I run out of some integer?

Question

As the title says, given a stock of integers 0-9, what is the last number I can write before I run out of some integer?

So if I'm given a stock of, say 10 for every number from 0 to 9, what is the last number I can write before I run out of some number. For example, with a stock of 2 I can write numbers 1 ... 10:

1 2 3 4 5 6 7 8 9 10

at this point my stock for ones is 0, and I cannot write 11. Also note that if I was given a stock of 3, I could still write only numbers 1 ... 10, because 11 would cost me 2 ones, which would leave my stock for ones at -1.

What I have come up 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 correct answer for fairly big stock sizes. With a stock size of 10^6 the code completes in ~2 seconds, and with a stock of 10^7 numbers it takes a whole 27 seconds. This is not good enough, since I'm looking for a solution that can handle stock sizes of as big as 10^16, so I probably need a O(log(n)) solution.

This is a homework like assignment, so I didn't come here without wrestling with this pickle for quite some time. I have failed to come up with anything similiar by googling, and wolfram alpha doesn't recognize any kind of pattern this gives.

What I have concluded so far is that ones will allways run out first. I have no proof, but it is so.

Can anyone come up with any piece of advice? Thanks a lot.

---

EDIT:

I have come up with and implemented an efficient way of finding the cost of numbers 1...n thanks to btilly's pointers (see his post and comments below. also marked as a solution). I will elaborate this further after I have implemented the binary search for finding the last number you can write with the given stock later today.

---

EDIT 2: The Solution

I had completely forgotten about this post, so my apologies for not editing in my solution earlier. I won't copy the actual implementation, though.

My code for finding the cost of a number does the following:

First, let us choose a number, e.g. 9999. Now we will get the cost by summing the cost of each tens of digits like so:

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 for 9999 is 4000.

the 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 for 256 is 156.

Implementing with this idea would make the program work only with numbers that have no digits 1 or 0, which is why further logic is needed. Let's call the method explained above C(n, d), where n is the number for which we are getting the cost for, and d is the d'th digit from n that we are currently working with. Let's also define a method D(n, d) that will return the d'th digit from n. Then we will 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)

With this the program will calculate the correct cost for a number efficiently. After this we simply apply a binary search for finding the number with the correct cost.

Answer 1

Step 1. Write an efficient function to calculate how much stock needs to be used to write all of the numbers up to N. (Hint: calculate everything that was used to write out the numbers in the last digit with 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 you can write with your amount of stock.