Number of substrings with length divisible by the number of 1 's in it | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countOfSubstrings ( string s ) { int n = s . length ( ) ; int x = sqrt ( n ) ; vector < int > ones ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '1' ) ones . push_back ( i ) ; } if ( ones . size ( ) == 0 ) return 0 ; ones . push_back ( n ) ; vector < int > totCount ( n * x + n ) ; int sum = 0 ; for ( int k = 0 ; k <= x ; k ++ ) { int now = 0 ; totCount [ k * n ] ++ ; for ( int j = 1 ; j <= n ; j ++ ) { if ( s [ j - 1 ] == '1' ) now ++ ; int index = j - k * now ; sum += totCount [ index + k * n ] ; totCount [ index + k * n ] ++ ; } now = 0 ; totCount [ k * n ] -- ; for ( int j = 1 ; j <= n ; j ++ ) { if ( s [ j - 1 ] == '1' ) now ++ ; int index = j - k * now ; totCount [ index + k * n ] -- ; } } int prefix_sum [ n ] ; memset ( prefix_sum , -1 , sizeof ( prefix_sum ) ) ; int cnt = 0 ; for ( int i = 0 ; i < n ; i ++ ) { prefix_sum [ i ] = cnt ; if ( s [ i ] == '1' ) cnt ++ ; } for ( int k = 0 ; k < n ; k ++ ) { for ( int j = 1 ; j <= ( n / x ) && prefix_sum [ k ] + j <= cnt ; j ++ ) { int l = ones [ prefix_sum [ k ] + j - 1 ] - k + 1 ; int r = ones [ prefix_sum [ k ] + j ] - k ; l = max ( l , j * ( x + 1 ) ) ; if ( l <= r ) { sum += r / j - ( l - 1 ) / j ; } } } return sum ; } int main ( ) { string S = "1111100000" ; cout << countOfSubstrings ( S ) ; return 0 ; }