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

Ответ 1

Подсчитайте числа, в которых не имеют цифру 2. Среди чисел менее 10 ^k имеется ровно 9 ^k Тогда остается рассматривать числа от 10 ^k до 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

Ответ 2

аргумент "цифра" - это тот, который мы хотим подсчитать, а аргумент "число" - там, где мы хотим подсчитать. Например, если мы хотим подсчитать вхождения "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;
}

Ответ 3

Учитывая число с цифрами ABCDEF, вы можете подсчитать количество "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);

То есть: if X >= 2, доля чисел, имеющих "2" в позиции nines + 1, равна 1/(X+1). Всего в этой позиции есть (T+1)/(X+1) '2. Если X < 2, то ни одно число на [0..T] не имеет "2" в этой позиции.

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

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

Ответ 4

вот как я буду писать код моего первого проекта (код Python)

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

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

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