Number of substrings with length divisible by the number of 1 's in it | Python3 program to count number of substring under given condition ; Function return count of such substring ; Selection of adequate x value ; Store where 1 's are located ; If there are no ones , then answer is 0 ; For ease of implementation ; Count storage ; Iterate on all k values less than fixed x ; Keeps a count of 1 's occured  during string traversal ; Iterate on string and modify the totCount ; If this character is 1 ; Add to the final sum / count ; Increase totCount at exterior position ; Reduce totCount at index + k * n ; Slightly modified prefix sum storage ; Number of 1 's till i-1 ; Traversing over string considering each position and finding bounds and count using the inequalities ; Calculating bounds for l and r ; If valid then add to answer ; Driver code
import math NEW_LINE def countOfSubstrings ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE x = int ( math . sqrt ( n ) ) NEW_LINE ones = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT ones . append ( i ) NEW_LINE DEDENT DEDENT if ( len ( ones ) == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ones . append ( n ) NEW_LINE totCount = [ 0 ] * ( n * x + n ) NEW_LINE sum = 0 NEW_LINE for k in range ( x + 1 ) : NEW_LINE INDENT now = 0 NEW_LINE totCount [ k * n ] += 1 NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( s [ j - 1 ] == '1' ) : NEW_LINE INDENT now += 1 NEW_LINE DEDENT index = j - k * now NEW_LINE sum += totCount [ index + k * n ] NEW_LINE totCount [ index + k * n ] += 1 NEW_LINE DEDENT now = 0 NEW_LINE totCount [ k * n ] -= 1 NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( s [ j - 1 ] == '1' ) : NEW_LINE INDENT now += 1 NEW_LINE DEDENT index = j - k * now NEW_LINE totCount [ index + k * n ] -= 1 NEW_LINE DEDENT DEDENT prefix_sum = [ - 1 ] * n NEW_LINE cnt = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT prefix_sum [ i ] = cnt NEW_LINE if ( s [ i ] == '1' ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT for k in range ( n ) : NEW_LINE INDENT j = 1 NEW_LINE while ( j <= ( n // x ) and prefix_sum [ k ] + j <= cnt ) : NEW_LINE INDENT l = ( ones [ prefix_sum [ k ] + j - 1 ] - k + 1 ) NEW_LINE r = ones [ prefix_sum [ k ] + j ] - k NEW_LINE l = max ( l , j * ( x + 1 ) ) NEW_LINE if ( l <= r ) : NEW_LINE INDENT sum += r // j - ( l - 1 ) // j NEW_LINE DEDENT j += 1 NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = "1111100000" NEW_LINE print ( countOfSubstrings ( S ) ) NEW_LINE DEDENT