Count of 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
def countSubstr ( s , k ) : NEW_LINE INDENT n = len ( s ) NEW_LINE l = n - 1 NEW_LINE r = n - 1 NEW_LINE arr = [ 0 ] * n NEW_LINE last_indexof1 = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT arr [ i ] = i NEW_LINE last_indexof1 = i NEW_LINE DEDENT else : NEW_LINE INDENT arr [ i ] = last_indexof1 NEW_LINE DEDENT DEDENT no_of_substr = 0 NEW_LINE for r in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT l = r NEW_LINE while ( l >= 0 and ( r - l + 1 ) <= 64 and int ( s [ l : r + 1 ] , 2 ) < k ) : NEW_LINE INDENT l -= 1 NEW_LINE DEDENT if ( r - l + 1 <= 64 ) : NEW_LINE INDENT no_of_substr += l + 1 NEW_LINE DEDENT else : NEW_LINE INDENT no_of_substr += arr [ l + 1 ] + 1 NEW_LINE DEDENT DEDENT return no_of_substr NEW_LINE DEDENT s = "11100" NEW_LINE k = 3 NEW_LINE print ( countSubstr ( s , k ) ) NEW_LINE