Count of substrings whose Decimal equivalent is greater than or equal to K | C ++ implementation to count the substrings whose decimal equivalent is greater than or equal to K ; Function to count number of substring whose decimal equivalent is greater than or equal to K ; Left pointer of the substring ; Right pointer of the substring ; Loop to maintain the last occurrence of the 1 in the string ; Variable to count the substring ; Loop to maintain the every possible end index of the substring ; Loop to find the substring whose decimal equivalent is greater than or equal to K ; Condition to check no of bits is out of bound ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; unsigned long long countSubstr ( string & s , int k ) { int n = s . length ( ) ; int l = n - 1 ; int r = n - 1 ; int arr [ n ] ; int last_indexof1 = -1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '1' ) { arr [ i ] = i ; last_indexof1 = i ; } else { arr [ i ] = last_indexof1 ; } } unsigned long long no_of_substr = 0 ; for ( r = n - 1 ; r >= 0 ; r -- ) { l = r ; while ( l >= 0 && ( r - l + 1 ) <= 64 && stoull ( s . substr ( l , r - l + 1 ) , 0 , 2 ) < k ) { l -- ; } if ( r - l + 1 <= 64 ) no_of_substr += l + 1 ; else { no_of_substr += arr [ l + 1 ] + 1 ; } } return no_of_substr ; } int main ( ) { string s = "11100" ; unsigned long long int k = 3 ; cout << countSubstr ( s , k ) ; }