Find all numbers in the range [L, R] whose binary representation contains a given pattern

user_6094884 0
Viewed 2504

Let L and R represent two positive integers, then we are required to find all the numbers in [L, R], i.e. L and R inclusive, that have 101 in their binary representation. For example, let L = 3 and R = 20 then 5(101) and 13(1101) are two such numbers.

Constraint

1 <= L <= R <= 10^18

My approach-

One obvious approach is to traverse from L to R and obtain the binary representation of each number and check if it contains 101, but that would take too much time given the constraint. Another way can be using Digit Dynamic Programming, more formally, if we can compute a function F(x), where x is a non negative integer and F(x) denotes the number of +ve integers smaller than or equal to x that satisfy the condition given in the question(i.e. it's binary representation contains 101) and if we assume that F(0) = 0 then the problem simply boils down to F(R) - F(L - 1). I have solved some Digit DP problems but unable to formulate this one, or maybe there is some other approach?

dynamic-programming algorithm
3 Answers

Simplest solution could be to split your number in 2 parts - given pattern and rest bits. Let's say biggest number is 5 bits long and given pattern is 3 - '101', so remaining part is 2 bits. Then you enumerate all variants for 2 bits and create numbers using them and joining with target pattern with all variants -

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'

then you just eliminate duplicates and limit range.

user_4323580

We can construct all the numbers less than an arbitrary target that do not have such a pattern by noting that we would be allowed to append 1 to any binary number that ends with 00, 11 or 01, and append 0 in any case. We can use regular "digit" dynamic programming that also stores the state of the last two digits, of which there are a total of four possibilities, then subtract the count from the target.

JavaScript code:

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}`)

user_20347870

If you don't count the time consumed by the binary to decimal transformation, probably something like @Slava's answer will be the fastest way. From a mathematical point of view, there are some shortcuts you can take as well. You could do a sieving, i.e start from 1 and check for the desired pattern. When you find one, in your example the first one would be 5, you know if you multiply it by 2, the pattern will still be there. So you found 5,10,20,40,80.... 10^18. After that you continue and check 7,9,11.... Note that this way you only need to check odd integers, because if an even integer contains the pattern 101, you know it is a multiple of a smaller odd integer that also contains 101. It really depends on the type of answer you are searching for, but like I said, if you are only looking for the fastest method, you should probably go for @Slava's answer.

user_100773710
Related