Учитывая число n, узнайте, сколько чисел имеют цифру 2 в диапазоне 0… n

Это вопрос интервью.

Given a number n, find out how many numbers have digit 2 in the range 0...n

Например ,

input = 13 output = 2 (2 and 12)

Я дал обычное решение O (n ^ 2), но есть ли лучший подход.

есть ли какой-нибудь "трюк"? формула, которая поможет мне получить ответ сразу

 Anil Kumar Arya01 июл. 2012 г., 09:38
Это вопрос перестановки.
 Fred Foo22 июн. 2012 г., 15:14
О (п & # XB2;)? Если вы имеете в виду, сгенерируйте числа и проверьте цифры, то есть O (n lg n), поскольку каждое число n представлено O (lg n) цифрами.
 ChaimKut07 янв. 2019 г., 21:51
@FredFoo, каждое число представлено log10 (n) цифрами, так что это O (nlog10 (n)) (количество цифр в базовом числе 10 равно log10 (n))

Ответы на вопрос(4)

def count2(n) :
    return [p for p in range(n+1) if '2' in str(p)]

и это вернет вам список с содержащим номером.

С точки зрения производительности это не так уж плохо, для n = 10 000 000 средняя итерация занимает около 5,5 секунд.

который мы хотим посчитать и аргументировать «число»; до того, где мы хотим посчитать. Например, если мы хотим сосчитать вхождения '1', от 0 до 12, вызовем функцию с цифрой = 1 и номером = 12, и она вернет число вхождений '1'.

int countOccurrences(int digit, int number)
{
    int counter = 0;
    for(int i=1; i<number; i++)
    {
        int j = i;
        while(j > 0)
        {
            if(j%10 == digit)
                counter++;
            j /= 10;
        }
    }
    return counter;
}
 03 июл. 2015 г., 03:45
Это учитывает двойки, а не то, сколько чисел имеют два. НАПРИМЕР. когда он достигает 22, он увеличивается вдвое, а не один раз, что неправильно.
 08 июл. 2014 г., 02:32
countOccurrences (1,20) = 3; //неправильно
 10 февр. 2014 г., 08:32
Объясните это некоторым объяснением ..
 15 июл. 2014 г., 17:54
Вы пытались выполнить этот метод? Возвращает 12, countOccurrence (1,20), а не 3.

вы можете сосчитать количество '2' в диапазонах.[0,F], [0,E9], [0,D99], [0,C999], [0,B9999] а также[0,A99999] и добавить их.

Тогда для диапазона[0, X9999...999]верхний номерT = X9999...999 можно записать как(X+1) * 10<sup>nines</sup> -1.

Число '2' в этом диапазоне равно:

((X >= 2 ? 1/(X + 1)) : 0) + nines/10 ) * (T + 1);

То есть: еслиX >= 2часть чисел, которые имеют «2»; в позиции девятки + 11/(X+1)Всего есть(T+1)/(X+1) '2' в этой позиции. ЕслиX < 2тогда никакое число на [0..T] не имеет «2»; в этой позиции.

Для других позиций цифр легко увидеть, что в каждой позиции цифр1/10 из чисел есть '2', так что есть(T+1)/10 '2' в положении 0,(T+1)/10 '2' в положении 1 и т. д. Всего(T+1) * nines / 10.

Сложность этого решения O (logN).

Подсчитайте числа, которые делаютnot иметь цифру 2. Среди чисел меньше 10kесть ровно 9k из них. Тогда осталось обработать цифры от 10k вn, где

10^k <= n < 10^(k+1)

что вы можете сделать, обрабатывая первые цифры по отдельности (случаи 2 и другие должны различаться), а затем первые 2 цифры и т. д.

Например, дляn = 2345мы находим там9^3 = 729 числа без цифры 2 ниже 1000. Снова 729 таких чисел в диапазоне от 1000 до 1999. Затем в диапазоне от 2000 до 2345 их нет, всего 1458, следовательно, числа, содержащие цифру 2,

2345 - 1458 = 887
 24 июн. 2012 г., 16:24
Если вы пишете числа с ведущими нулями, цифры от 0 до10^k - 1 это именно те цифры, которые вы можете написать с точноk цифры. Для каждой из цифр есть 9 (== 10 - 1) возможные варианты (0,1,3,4,5,6,7,8,9). Выборы независимы, поэтому общее количество вариантов является произведением количества вариантов для каждой цифры,9*9*...*9 = 9^k, Если бы вы были после чисел, не содержащих ни цифры 2, ни цифры 5, это было бы8^k (8 = 10 - 2). Тот же принцип справедлив для представлений чисел в других базисах. Однако, так как числа действительно не имеют ведущих нулей, продолжение ...
 24 июн. 2012 г., 16:29
..., запрещая цифру 0, немного отличается. Затем вы не можете добавить начальные нули, чтобы получить все числа одинаковой длины, а количество чисел ниже.10^k что цифра 0 не имеет9^1 + 9^2 + 9^3 + ... + 9^k = 9 * (9^k - 1)/8, Если вы запрещаете 0 иd другие цифры, оставляяe = 9-d соответствующие цифры, вы получаетеe^1 + e^2 + ... + e^k = e * (e^k - 1)/(e-1), (Заменить 9 наbase-1 для баз, отличных от 10.)
 24 июн. 2012 г., 16:06
Не могли бы вы объяснить, как вы получили 9 ^ k чисел, я не очень хорош в комбинаторике.
 25 июн. 2012 г., 00:03
Прекрасное спасибо за хорошее объяснение.

Ваш ответ на вопрос