时间戳

首页 > 解决方案 > 如何找到第 x 个十进制数？

algorithm - 如何找到第 x 个十进制数？

问题描述

Hackerrank 有一个称为十进制数的问题，它本质上是具有 0-9 位数值的数字，但使用 2 的幂进行幂运算。问题要求我们显示第 x 个十进制数。这个问题还有另一个转折点。多个十进制数可以等于同一个十进制数。例如，十进制的 4 可以是十进制的 100、20、12 和 4。

起初，我认为找出给定十进制数有多少个十进制数会很有帮助。我查阅了这篇文章以获得一些帮助（https://math.stackexchange.com/questions/3540243/whats-the-number-of-decibinary-numbers-that-evaluate-to-given-decimal-number）。这篇文章有点难以理解，但后来我也意识到，即使我们有一个十进制数可以有多少个十进制数，这也无助于找到它们（至少据我所知），这是最初的目标问题。

我确实意识到，对于任何十进制数，它的最大十进制数只是它的二进制表示。例如，对于 4，它是 100。因此，蛮力方法是检查每个十进制数在此范围内的所有数字，看看它们的十进制表示是否计算为给定的十进制数，但很明显，这种方法永远不会由于输入约束将 x 定义为从 1 到 10^16，因此通过。不仅如此，我们还必须为 aq 数量的查询找到第 x 个十进制数，其中 q 从 1 到 10^5。

这个问题属于 dp 部分，但我很困惑如何使用 dp 或者它是如何可能的。为了计算第 x 个十进制数 q 次（在上面的蛮力方法中进行了描述），最好使用一个表格（就像问题所暗示的那样）。但为此，我们需要存储和计算 10^16 个整数，因为这就是 x 的大小。假设一个整数是 4 字节，4B * 10^16 ~= 4B * (2^3)^16 = 2^50 字节。

有人可以解释一下如何以最佳方式解决这个问题。我还是 CP 的新手，所以如果我在某些方面犯了错误，请告诉我。

（有关完整的问题陈述，请参见下面的链接）： https ://www.hackerrank.com/challenges/decibinary-numbers/problem

标签： algorithmdynamic-programmingnumber-systems

解决方案

这可以用大约 80 MB 的数据来解决。我不会给出代码，但我会解释策略。

构建一个查找，为您提供使用前几位count[n][i]获取十进制数的多种方法。您首先在任何地方插入，然后在. 现在开始使用规则填写：ni01count[0][0]

count[n][i] = count[n][i-1] + count[n - 2**i][i-1] + count[n - 2*2**i][i-1] + ... + count[n - 9*2**i][i-1]

事实证明，您只需要前 19 位数字，并且n最多只需要2**19-1. 并且计数都适合 8 byte longs。

一旦你有了它，创建第二个数据结构count_below[n]，它是多少十进制数的计数将给出小于n. 使用与以前相同的范围n。

现在查找进行如下。首先，您进行二进制搜索count_below以找到最后一个小于您的目标数字的值。从您的查询中减去count_below，您知道您想要该值的哪个十进制数。

接下来，搜索count[n][i]以找到i这样的方式，您可以使用i数字而不是更少的方式获得目标查询。这将是您答案的首位数字的位置。然后，您从查询中减去count[n][i-1]（所有数字较少的十进制数）。然后减去 off count[n-2**i][i-1], count[n-2* 2**i][i-1], ...count[n-8*2**i][i-1]直到找到前导数字。现在，您从该值中减去该数字的贡献，并重复逻辑以找到具有较少数字的较小值的正确十进制。

这是一个工作示例来澄清。首先是前 3 位及以下的数据结构2**3 - 1：

count = [
  [1, 1, 1, 1], # sum 0
  [0, 1, 1, 1], # sum 1
  [0, 1, 2, 2], # sum 2
  [0, 1, 2, 2], # sum 3
  [0, 1, 3, 4], # sum 4
  [0, 1, 3, 4], # sum 5
  [0, 1, 4, 6], # sum 6
  [0, 1, 4, 6], # sum 7
]

count_below = [
    0, 1, 2, 4, 6, 10, 14, 20, 26, ...
]

让我们找到第20个。

  1. count_below[6]是 14 和count_below[7]20 所以我们的十进制和是6。
  2. 我们想要20 - count_below[6] = 6十进制和 6 的 th 十进制。
  3. count[6][2]是 4count[6][3]而是 6 所以我们有一个非零的第三个数字。
  4. 我们想要count[6][3] - count[6][2] = 2第三位非零的 。
  5. count[1][6 - 2**2]是 2，所以 2 有第三个数字 1。
  6. 第三个数字是1
  7. 我们现在正在寻找其十进制和为 的第二个十进制2。
  8. count[2][1]是 1 和count[2][2]2 所以它有一个非零的第二个数字。
  9. 我们想要count[2][2] - count[2][1] = 1第二个数字非零的 st。
  10. 第二个数字是1
  11. 其余为 0，因为2 - 2**1 = 0.

因此你会发现答案是 110。

现在对于这么小的数字，这是很多工作。但即使是最困难的查找，您也只需要大约 20 步的二进制搜索来找到您的十进制和，另外 20 步来找到第一个非零数字的位置，并且对于这些数字中的每一个，您将必须进行 1-9 次不同的计算才能找到该数字。这意味着只有数百次计算才能找到数字。

推荐阅读