给定0-9的整数,在用完一些整数之前,我能写出的最后一个数字是多少？

Question

正如标题所说,给定0-9的整数,在我用完一些整数之前,我能写出的最后一个数字是多少？

因此,如果我给出了一个库存,比如从0到9的每个数字为10,那么在我用完一些数字之前,我可以写的最后一个数字是多少.例如,股票为2我可以写数字1 ... 10:

1 2 3 4 5 6 7 8 9 10

在这一点上我的股票是0,我不能写11.还要注意,如果给我一个3的股票,我仍然只能编写1 ... 10的数字,因为11将花费我2个,这将将我的股票留给-1.

到目前为止我所得到的:

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));

}

}

有了这个,我可以得到相当大的股票大小的正确答案.库存大小为10 ^ 6时,代码在~2秒内完成,并且库存为10 ^ 7个数字需要整整27秒.这还不够好,因为我正在寻找一种能够处理大到10 ^ 16的库存大小的解决方案,所以我可能需要一个O(log(n))解决方案.

这是一个像作业一样的作业,所以我没有在没有与这个泡菜摔跤很长一段时间来到这里.我没有想出任何类似于谷歌搜索的东西,而且沃尔夫拉姆阿尔法不承认这给出了任何一种模式.

到目前为止我得出的结论是,总会先消失.我没有证据,但事实确实如此.

任何人都可以提出任何建议吗？非常感谢.

---

编辑:

我已经提出并实现了一种有效的方法来查找数字1 ... n的成本,这要归功于btilly的指针(请参阅下面的帖子和评论.也标记为解决方案).在我实施二进制搜索以找到您今天晚些时候可以使用给定股票编写的最后一个数字后,我将进一步详细说明.

---

编辑2:解决方案

我完全忘记了这篇文章,所以我很抱歉没有在我的解决方案中进行编辑.不过,我不会复制实际的实现.

我查找数字成本的代码执行以下操作:

首先,让我们选择一个数字,例如9999.现在我们将通过总计每个数十位的成本得到成本,如下所示:

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

因此9999的成本是4000.

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

因此256的成本是156.

使用这个想法实现将使程序仅使用没有数字1或0的数字,这就是为什么需要进一步的逻辑.让我们把上面解释的方法在C(n,d) ,其中ñ是,我们越来越对成本的数量,d是d "日从数字ň,我们目前正与合作.我们还定义一个方法D(n,d),它将从n返回第d '个数字.然后我们将应用以下逻辑:

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)

有了这个,程序将有效地计算数字的正确成本.在此之后,我们只需应用二进制搜索来找到具有正确成本的数字.

Answer 1

步骤 1. 编写一个高效的函数来计算需要使用多少库存才能写入 为止的所有数字N。（提示：用公式计算用于写出最后一位数字的所有内容，然后使用递归计算其他数字中使用的所有内容。）

步骤 2. 进行二分查找，找到您可以用库存量写出的最后一个数字。