Number of substrings with length divisible by the number of 1 's in it | Function return count of such substring ; Mark 1 at those indices where '1' appears ; Take prefix sum ; Iterate through all the substrings ; Driver Code
def countOfSubstrings ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE prefix_sum = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT prefix_sum [ i ] = 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , n , 1 ) : NEW_LINE INDENT prefix_sum [ i ] += prefix_sum [ i - 1 ] NEW_LINE DEDENT answer = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i , n , 1 ) : NEW_LINE INDENT if ( i - 1 >= 0 ) : NEW_LINE INDENT countOfOnes = prefix_sum [ j ] - prefix_sum [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT countOfOnes = prefix_sum [ j ] NEW_LINE DEDENT length = j - i + 1 NEW_LINE if ( countOfOnes > 0 and length % countOfOnes == 0 ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = "1111100000" NEW_LINE print ( countOfSubstrings ( S ) ) NEW_LINE DEDENT