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()
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