Number of substrings with length divisible by the number of 1 's in it | 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
function countOfSubstrings ( s ) { var n = s . length ; var x = parseInt ( Math . sqrt ( n ) ) ; var ones = [ ] ; for ( var i = 0 ; i < n ; i ++ ) { if ( s [ i ] == ' ' ) ones . push ( i ) ; } if ( ones . length == 0 ) return 0 ; ones . push ( n ) ; var totCount = Array ( n * x + n ) . fill ( 0 ) ; var sum = 0 ; for ( var k = 0 ; k <= x ; k ++ ) { var now = 0 ; totCount [ k * n ] ++ ; for ( var j = 1 ; j <= n ; j ++ ) { if ( s [ j - 1 ] == ' ' ) now ++ ; var index = j - k * now ; sum += totCount [ index + k * n ] ; totCount [ index + k * n ] ++ ; } now = 0 ; totCount [ k * n ] -- ; for ( var j = 1 ; j <= n ; j ++ ) { if ( s [ j - 1 ] == ' ' ) now ++ ; var index = j - k * now ; totCount [ index + k * n ] -- ; } } var prefix_sum = Array ( n ) . fill ( - 1 ) ; var cnt = 0 ; for ( var i = 0 ; i < n ; i ++ ) { prefix_sum [ i ] = cnt ; if ( s [ i ] == ' ' ) cnt ++ ; } for ( var k = 0 ; k < n ; k ++ ) { for ( var j = 1 ; j <= parseInt ( n / x ) && prefix_sum [ k ] + j <= cnt ; j ++ ) { var l = ones [ prefix_sum [ k ] + j - 1 ] - k + 1 ; var r = ones [ prefix_sum [ k ] + j ] - k ; l = Math . max ( l , j * ( x + 1 ) ) ; if ( l <= r ) { sum += parseInt ( r / j ) - parseInt ( ( l - 1 ) / j ) ; } } } return sum ; } var S = " " ; document . write ( countOfSubstrings ( S ) ) ;