Given a stock of integers 0-9, what is the last nu

问题:

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.

回答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.

回答2:

We can calculate the answer directly. A recursive formula can determine how much stock is needed to get from 1 to numbers that are powers 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 gets complicated is accounting for the extra 1's needed when our calculation lands after the first multiple of any of the above coefficients; for example, on the second multiple of 10 (11-19) we need an extra 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