Это вопрос интервью.
Учитывая число n, выясните, сколько чисел имеет цифру 2 в диапазоне 0... n
Например,
input = 13 output = 2 (2 и 12)
Я дал обычное решение O (n ^ 2), но есть лучший подход.
есть ли какая-либо формула "трюка", которая поможет мне сразу же получить ответ.
Подсчитайте числа, в которых не имеют цифру 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
аргумент "цифра" - это тот, который мы хотим подсчитать, а аргумент "число" - там, где мы хотим подсчитать. Например, если мы хотим подсчитать вхождения "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;
}
Учитывая число с цифрами 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).
вот как я буду писать код моего первого проекта (код Python)
def count2(n) :
return [p for p in range(n+1) if '2' in str(p)]
и это вернет вам список с содержащим номером.
С точки зрения производительности это не так уж плохо, для n = 10 000 000 средняя итерация занимает около 5,5 секунд.