×

# WITBIT - UNOFFICIAL EDITORIAL

 0 1 PROBLEM LINK Contest DIFFICULTY medium PROBLEM 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. EXPLANATION 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 way. 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. if(fl){ 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 }else 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 forward. } return res;  Link for AC Solution: this asked 11 Feb, 23:11 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,172