2 作为从 0 到 n 的数字中的数字出现的次数，没有得到 O(n) 解决方案？

Question

This the GFG Link 在这个 link 中，我无法直观地了解我们是如何计算 2 的数字的，我的疑问是，如果我们正在计算范围内的 6000 位数字，如以下描述中所述，那么为什么我们只是将数字除以 10 并返回它，如果有人可以帮助我，请用示例 post 你的答案

Case digits < 2
Consider the value x = 61523 and digit at index d = 3 (here indexes are considered from right and rightmost index is 0). We observe that x[d] = 1. There are 2s at the 3rd digit in the ranges 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999, and 52000 – 52999. So there are 6000 2’s total in the 3rd digit. This is the same amount as if we were just counting all the 2s in the 3rd digit between 1 and 60000.
In other words, we can round down to the nearest 10d+1, and then divide by 10, to compute the number of 2s in the d-th digit.
if x[d) < 2: count2sinRangeAtDigit(x, d) =
  Compute y = round down to nearest 10d+1 
  return y/10 
Case digit > 2
Now, let’s look at the case where d-th digit (from right) of x is greater than 2 (x[d] > 2). We can apply almost the exact same logic to see that there are the same number of 2s in the 3rd digit in the range 0 – 63525 as there as in the range 0 – 70000. So, rather than rounding down, we round up.
if x[d) > 2: count2sinRangeAtDigit(x, d) =
  Compute y = round down to nearest 10d+1 
  return y / 10 
Case digit = 2
The final case may be the trickiest, but it follows from the earlier logic. Consider x = 62523 and d = 3. We know that there are the same ranges of 2s from before (that is, the ranges 2000 – 2999, 12000 – 12999, … , 52000 – 52999). How many appear in the 3rd digit in the final, partial range from 62000 – 62523? Well, that should be pretty easy. It’s just 524 (62000, 62001, … , 62523).
if x[d] = 2: count2sinRangeAtDigit(x, d) = 
   Compute y = round down to nearest 10d+1 
   Compute z = right side of x (i.e., x%  10d)
   return y/10 + z + 1**// here why we are doing it ,what is the logic behind this approach**

上面给出的解释并不完全清楚，这就是我在这里问的原因谢谢

Answer 1

对我来说，这个解释也很奇怪。另请注意，真正的复杂性是 O(log(n))，因为它取决于数字长度（数字计数）。

考虑下一个例子：我们有数字 6125.

在第一轮我们需要计算从0到[=的所有数字中最右边的数字有多少2被满足 10=]。我们将数字向下舍入为 6120，向上舍入为 6130。最后一位数字是 5>2，所以我们有 613 个区间，每个区间包含一个数字 2 作为最后一位数字 - 这里我们计算最后 2 的数字，例如 2,12,22,..1352,..,6122.

在第二轮中，我们需要计算 0 中的所有数字中有多少 2 作为第二个（右起）数字 被满足 ] 到 6125。我们将数字向下舍入为 6100，向上舍入为 6200。我们还有 right=5。数字是2，所以我们有61个区间，每个区间包含十位数字2在第二位（20..29, 120..129... 6020..6029 ).我们添加 61*10。我们还必须为值 6120..6125[=45 添加 5+1 2 =]

在第三轮，我们需要计算0的所有数字中有多少2满足作为第三个（右起）数字 ] 到 6125。我们将数字向下舍入为 6000，向上舍入为 7000。数字是1，所以我们有6 intervals，每个区间在第三位（200.299.. 5200..5299）包含一百个数字2。所以添加 6*100.

我想现在很清楚了，我们添加1区间，thousand of 2的（2000.2999）作为最左边的数字（6>2）

2 作为从 0 到 n 的数字中的数字出现的次数，没有得到 O(n) 解决方案？

Number of occurrences of 2 as a digit in numbers from 0 to n , Not getting the O(n) solution?

algorithm

math

number-theory