Number of substrings with length divisible by the number of 1 's in it | Java 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
import java . util . * ; class GFG { static int countOfSubStrings ( String s ) { int n = s . length ( ) ; int [ ] prefix_sum = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . charAt ( 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 ; } public static void main ( String [ ] args ) { String S = "1111100000" ; System . out . print ( countOfSubStrings ( S ) ) ; } }