Мне нужно найти n-е число, которое содержит цифру k или делится на k. (2 <= k <= 9)

Question

Пример - если n = 15 & k = 3 Ответ: 33 (3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31 , 32, 33)

Я начал следующую последовательность, но не мог сформулировать его

для кратных 3 -> 3 + 3 + 3 + 4 + 3 + 3 + 4 + 3 + 3 + 4

для вмещения цифры 3 ->

{

диапазона в дифф = 100 -> 1 + 1 + 1 + 10 + 1 + 1 + 1 + 1 + 1 + 1 = F (п) говорят ;

диапазон в diff = 1000 -> f (n) + f (n) + f (n) + 10 * f (n) + f (n) + f (n) + f (n) + f (n) + f (n) + f (n) = ff (n) say

диапазон в diff = 10000 -> ff (n) + ff (n) + ff (n) + 10 * ff (n) + ff (n) + ff (n) + ff (n) + ff (n) + ff (n) + ff (n)

также идет дальше.

}

я должен ответить лучше, чем O (N) или O (1), если это возможно, пожалуйста, не предлагают такие методы, как проверить каждое число в цикле. Благодарю.

Редактировать-Я искал всюду, но не мог найти ответ нигде, так что это не дубликат.

Answer 1

Вот один из способов подумать об этом, который мог бы указать вам хотя бы на одно направление (или, альтернативно, погоню за дикими гусями). Отделите два вопроса и устраните наложенные результаты:

(1) Сколько j-digit цифры делятся на k? [j 9's/k] - [(j-1) 9's/k]

(2) Сколько номеров j-digit содержит цифру k? 9 * 10^(k-1) - 8 x 9^(k-1)

Теперь мы должны вычесть j-digit номера, которые как делится на k и включают цифру k. Но сколько их?

Используйте правила делимости для рассмотрения различных случаев. Например:

k = 2 
If k is the rightmost digit, any combination of the previous j-1 digits would work. 
Otherwise, only combinations with 0,4,6 or 8 as the rightmost digit would work. 

k = 5 
If k is the rightmost digit, any combination of the previous j-1 digits would work. 
Otherwise, only combinations with 0 or 5 as the rightmost digit would work. 

etc. 

(Приложение:. Я задал вопрос о комбинаторной math.stackexchange и получил некоторые интересные answers А вот ссылка на вопрос OP на math.stackexchange: https://math.stackexchange.com/questions/1884303/the-n-th-number-that-contains-the-digit-k-or-is-divisible-by-k-2-le-k-l)

Answer 2

Вслед за גלעד ברקן's answer, если у вас есть O (1) способ вычисления d(j, k) = числа с по крайней мере одной цифрой k до j, отбрасывание чисел, делящихся на k, то вы можете рассчитать e(j, k) = числа, по крайней мере, по значению k или делится на k под j как j/k + d(j, k).

Это позволяет найти f(n, k) с бинарным поиском, так как k <= f(n, k) <= k*n и e(j, k) = n <=> f(n, k) = j: вы, по сути пытаетесь угадать, какой j дадут ожидаемый n в O (журнал N) пытается.

Я согласен с наблюдением גלעד בר observation относительно правил делимости для расчета d(j, k) эффективно; но они не являются тривиальными для реализации, за исключением k=5 и k=2.

Я очень сомневаюсь, что вы можете улучшить O (log n) для этой проблемы; и он может быть даже недоступен для некоторых значений k.

Answer 3

Это сложнее, чем я думал, но я думаю, что я нашел решение для простейшего случая (k = 2).

Сначала я попытался упростить задачу, задав следующий вопрос: в какой позиции в последовательности есть номера 10^i * k, где i = 1, 2, 3, ...? При к = 2 числа 20, 200, 2000, ...

i k                 n 
1 2 20/2              = 10 
2 2 200/2 + 2* 5            = 110 
3 2 2000/2 + 2* 50  + 18* 5         = 1190 
4 2 20000/2 + 2*500  + 18*50   + 162*5     = 12710 
i 2 10^i + 2*10^(i-1)/2 + 18*10^(i-2)/2 + 162*10^(i-3)/2 + ?*10^(i-4)/2 + ... 

В последней строке я попытался выразить узор. Первая часть - это число, делящееся на 2. Тогда есть i-1 дополнительные части для нечетных чисел с 2 в первой позиции, секунде и так далее. Трудная часть состоит в том, чтобы вычислить факторы (2, 18, 162, ...).

Здесь функция, возвращающая новый фактор для любого I:

f(i) = 2 * 10^(i-2) - sum(10^(i-x-1)*f(x), x from 2 to i-1) = 2 * 9^(i-2) [thx @m69] 
f(2) = 2 
f(3) = 2*10 - (1*2) = 18 
f(4) = 2*100 - (10*2 + 1*18) = 162 
f(5) = 2*1000 - (100*2 + 10*18 + 1*162) = 1458 

Таким образом, используя эту информацию, мы можем прийти по следующему алгоритму:

Найти наибольшее число 10^i*2, которая не превышает позицию , (Если n находится в диапазоне [positionOf(10^i*2), positionOf(10^i*2) + (10^i)], то мы уже знаем решение: 10^i*2 + (n - positionOf(10^i*2)).Если, если мы найдем, что i = 2, мы знаем, что следующие 100 значений находятся в последовательности: [201, 300], поэтому, если 110 < = n < = 210, то решение 200+ (п-110) = п + 90.)

int nn = positionOf(10^i * 2); 
int s = 10^i * 2; 
for (int ii = i; ii >= 0; ii--) { 
    for (int j = 1; j < 10; j++) { 
    if (j == 1 || j == 6) { 
     if (n <= nn + 10^ii) 
     return s + nn - n; 
     nn += 10^ii; 
     s += 10^ii; 
     int tmp = positionOf(10^ii); 
     if (nn + tmp > n) 
     break; 
     nn += tmp; 
     s += 10^ii; 
    } else { 
     int tmp = positionOf(10^ii * 2); 
     if (nn + tmp > n) 
     break; 
     nn += tmp; 
     s += 10^ii * 2; 
    } 
    } 
} 
return s; 

Это только непроверенные неполная псевдо-код (я знаю, что вы не можете использовать ^ в Java), ii = 1 или 0 необходимо рассматривать как особый случай, это отсутствует и как найти i тоже не показано, или ответ будет слишком длинным.