Найти все числа в диапазоне [L, R], двоичное представление которых содержит заданный шаблон

Question

Пусть L и R представляют два натуральных числа, тогда мы должны найти все числа в [L, R], т.е. L и R включительно, которые имеют 101 в двоичном представлении. Например, пусть L = 3 и R = 20, тогда 5 (101) и 13 (1101) - два таких числа.

Ограничение

1 <= L <= R <= 10 ^18 </p>

Мой подход -

Один очевидный подход - перейти от L к R и получить двоичное представление каждого числа и проверить, содержит ли оно 101, но это займет слишком много времени, учитываяограничение. Другим способом может быть использование Digit Dynamic Programming, более формально, если мы можем вычислить функцию F (x), где x - неотрицательное целое число, а F (x) обозначает число целых + ve, меньших или равных x, которые удовлетворяютусловие, данное в вопросе (т. е. его двоичное представление содержит 101), и если мы предположим, что F (0) = 0, то проблема просто сводится к F (R) - F (L - 1). Я решил некоторые проблемы с Digit DP, но не смог сформулировать эту, или, может быть, есть какой-то другой подход?

Answer 1

Мы можем построить все числа, меньшие произвольной цели, у которых нет такого шаблона, отметив, что нам будет разрешено добавлять 1 к любому двоичному числу, которое заканчивается на 00, 11 или 01, и добавлять 0 в любом случае,Мы можем использовать обычное «цифровое» динамическое программирование, которое также хранит состояние двух последних цифр, из которых имеется всего четыре возможности, а затем вычитает счет из цели.

Код JavaScript:

function f(s, i, x, y, limited){
  if (i == s.length - 1){
    if ((limited && s[i] == '0') || (x + y == '10'))
      return 1
    else
      return 2
    
  // Prefix has less than two digits
  } else if (x == -1){
    if (limited && s[i] == 0){
      return f(s, i+1, y, '0', true)
      
    } else {
      return f(s, i+1, y, '0', false) +
        f(s, i+1, y, '1', limited)
    }
    
  // Prefix has at least two digits
  } else {
    if (limited && s[i] == 0){
      return f(s, i+1, y, '0', true)
      
    } else {
      result = f(s, i+1, y, '0', false)
      
      if (x + y != '10')
        result += f(s, i+1, y, '1', limited)
      
      return result
    }
  }
}

var n = 2555
var s = n.toString(2)
var c = 0

c += f(s, 1, -1, '0', false)
c += f(s, 1, -1, '1', true)

// (+ 1) removes the count for zero
console.log(`Count without the pattern: ${c}\nSolution: ${n - c + 1}`)

// Brute force
c = 0
for (let x=1; x<=n; x++)
  if (/101/.test(x.toString(2)))
    c++

console.log(`Brute force: ${c}`)

Answer 2

Самое простое решение может быть разделить ваш номер на 2 части - заданный шаблон и остальные биты. Допустим, наибольшее число имеет длину 5 битов, а заданный шаблон - 3 - 101, поэтому оставшаяся часть составляет 2 бита. Затем вы перечисляете все варианты для 2 битов и создаете числа, используя их и объединяясь с целевым шаблоном со всеми вариантами -

00 gives you '00 101' '0 101 0' '101 00'
01 gives you '01 101' '0 101 0' '101 01'
10 gives you '10 101' '1 101 0' '101 10'
11 gives you '11 101' '1 101 1' '101 11'

, затем вы просто исключаете дубликаты и ограничивает диапазон.

Answer 3

Если вы не посчитаете время, затрачиваемое двоичным на десятичное преобразование, вероятно, что-то вроде ответа @ Slava будет самым быстрым. С математической точки зрения, вы также можете воспользоваться некоторыми ярлыками. Вы можете сделать просеивание, то есть начать с 1 и проверить желаемый шаблон. Когда вы найдете один, в вашем примере первым будет 5, вы знаете, если вы умножите его на 2, шаблон все равно будет там. Итак, вы нашли 5,10,20,40,80.... 10^18. После этого вы продолжаете и проверяете 7,9,11 .... Обратите внимание, что таким образом вам нужно проверять только нечетные целые числа, потому что если четное целое число содержит шаблон 101, вы знаете, что оно кратно меньшему нечетному целому числуэто также содержит 101. Это действительно зависит от типа ответа, который вы ищете, но, как я уже сказал, если вы ищете только самый быстрый метод, вам, вероятно, следует обратиться к ответу @ Slava.