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 ; Mark 1 at those indices where '1' appears ; Take prefix sum ; Iterate through all the substrings ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countOfSubstrings ( string s ) { int n = s . length ( ) ; int prefix_sum [ n ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '1' ) prefix_sum [ i ] = 1 ; } for ( int i = 1 ; i < n ; i ++ ) prefix_sum [ i ] += prefix_sum [ i - 1 ] ; int answer = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { int countOfOnes = prefix_sum [ j ] - ( i - 1 >= 0 ? prefix_sum [ i - 1 ] : 0 ) ; int length = j - i + 1 ; if ( countOfOnes > 0 && length % countOfOnes == 0 ) answer ++ ; } } return answer ; } int main ( ) { string S = "1111100000" ; cout << countOfSubstrings ( S ) ; return 0 ; }