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

15

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

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), но есть ли лучший подход.

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

О (п & # XB2;)? Если вы имеете в виду, сгенерируйте числа и проверьте цифры, то есть O (n lg n), поскольку каждое число n представлено O (lg n) цифрами. Fred Foo
Это вопрос перестановки. Anil Kumar Arya
@FredFoo, каждое число представлено log10 (n) цифрами, так что это O (nlog10 (n)) (количество цифр в базовом числе 10 равно log10 (n)) ChaimKut

Ваш Ответ

4   ответа
0

вы можете сосчитать количество '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).

0

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

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

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

26

Подсчитайте числа, которые делают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
Прекрасное спасибо за хорошее объяснение.
..., запрещая цифру 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.)
Не могли бы вы объяснить, как вы получили 9 ^ k чисел, я не очень хорош в комбинаторике.
Если вы пишете числа с ведущими нулями, цифры от 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). Тот же принцип справедлив для представлений чисел в других базисах. Однако, так как числа действительно не имеют ведущих нулей, продолжение ...
1

который мы хотим посчитать и аргументировать «число»; до того, где мы хотим посчитать. Например, если мы хотим сосчитать вхождения '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;
}
Объясните это некоторым объяснением ..
Вы пытались выполнить этот метод? Возвращает 12, countOccurrence (1,20), а не 3.
countOccurrences (1,20) = 3; //неправильно
Это учитывает двойки, а не то, сколько чисел имеют два. НАПРИМЕР. когда он достигает 22, он увеличивается вдвое, а не один раз, что неправильно.

Похожие вопросы