You are not logged in. Please login at to post your questions!






Given a range of integers [L, R] and we have to find the count of such integer i where L≤i≤R and binary representation of i contains the pattern "110" as a substring, where L, R can potentially go up to 10^18.

As we need to find the information of substring "110", whether it is present in the given range we need to convert the given numbers into Binary Strings. We can simply do that in C++ using inbuilt function std::string s = std::bitset< 64 >( number ).to_string() :p

We can solve now with Dynamic Programming we require three arguments that are:
pos: current index of the number which we are forming.
cnt: which count if we have counted the substring "110". If yes then we return 1 way of having a number which has "110" in the given number.
flag: which tell us if the given number is smaller than the given number.

LL go(LL pos, LL cnt, int fl){

// Base Case of Our Function

 if(pos == num.size()){
    if(cnt == 3)    return 1;  //If cnt = 3 that means we got one of substring "110", so we return one 
    return 0;                  //If cnt != 3 we return 0

int lmt;                    // Which tells us the limiting or ending value for the current position.
LL &res = DP[pos][cnt][fl]; // If result is already calculated then return it as it was.
if(res != -1)   return res;

res = 0; //If result was not calculated then make dp[pos][cnt][fl] = 0 and calculate it now.

    lmt = 1;         // If fl == 1, it tells us that the number which will be made will be smaller than 
                        given number so we can give its limit 0 to 1 
    lmt = num[pos];  // if fl == 0, it tells us that the current number is equal to the given number so 
                         we can place the digit at this given position either 0 to num[pos].

for(int i to lmt){
    int nf = fl;
    int ncnt = cnt;
    if(fl == 0 and i < lmt) nf = 1;         // The number is getting smaller at this position
    if(i == 1 and (cnt == 0 || cnt == 1))    // If the current[index] = 1 and we have cnt = 0,
    ++ncnt                                      means that none of 1 of "110" occured till now 
                                                **or** we have cnt = 1, means one 1 of "110" have 
                                                been occured

    if(i == 0 and cnt == 2)                  // If we got two 1 of "110" so we can now needs to search  
    ++cnt                                      for zero to make our search complete.

    if(i == 0 and cnt == 1)                  // If we got zero after the cnt of 1, like this "10...." so
    nct = 0                                     we will be making ncnt = 0 again and we need to search 
                                                string "110" again in the given number

    res += go(pos+1, ncnt, nf);              // We will be moving our current index postion by one step 

return res;

Link for AC Solution: this

asked 11 Feb, 23:11

ayush1111's gravatar image

accept rate: 0%

edited 11 Feb, 23:36

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 11 Feb, 23:11

question was seen: 85 times

last updated: 11 Feb, 23:36