Количество вхождений 2 как di git в числах от 0 до n, не получено решение O (n)?

Question

Это ссылка GFG В этой ссылке я не могу получить ничего интуитивного представления о том, как мы вычисляем число 2 как di git in. Я сомневаюсь, что мы считаем 6000 цифр в диапазоне, как объяснено в приведенном ниже описании, тогда почему мы просто делим число на 10 и возвращаем его. Если кто-нибудь может мне помочь, отправьте свой ответ с примерами

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)), потому что она зависит от длины номера (di git count).

Рассмотрим следующий пример: у нас есть номер 6125.

В первом раунде нам нужно подсчитать, сколько 2 соответствует как крайний правый di git во всех числах от 0 до 6125. Мы округляем число до 6120 и до 6130. Последний di git равен 5>2, поэтому у нас есть 613 интервалов, каждый интервал содержит один di git 2 в качестве последнего di git - здесь мы считаем последние 2 в числах, например 2,12,22,..1352,..,6122.

Во втором раунде нам нужно подсчитать, сколько 2 встречается как второе (справа) di git во всех числах от 0 на 6125. Мы округляем число до 6100 и до 6200. Также у нас есть right=5. Di git равно 2, поэтому у нас есть 61 интервал , каждый интервал содержит десять цифр 2 на втором месте (20..29, 120..129... 6020..6029). Добавляем 61*10. Также мы должны добавить 5+1 2 для значений 61 2 0..61 2 5

В третьем раунде нам нужно вычислить, как многие 2 встречаются как третье (справа) di git во всех числах от 0 до 6125. Мы округляем число до 6000 и до 7000. Di git равно 1, поэтому у нас есть 6 intervals, каждый интервал содержит сотню di git 2 на третьем месте (200.299.. 5200..5299). Так что добавьте 6*100.

Я думаю, теперь ясно, что мы добавляем 1 интервал с thousand of 2 (2000.2999) как крайний левый di git (6>2)