Count of substrings in a Binary String that contains more 1 s than 0 s | Function to merge two partitions such that the merged array is sorted ; Counting inversions ; Function to implement merge sort ; Function to calculate number of inversions in a given array ; Calculate the number of inversions ; Return the number of inversions ; Function to count the number of substrings that contains more 1 s than 0 s ; Stores the prefix sum array ; Stores the count of valid substrings ; Driver Code ; Given Input ; Function Call
def merge ( v , left , mid , right , inversions ) : NEW_LINE INDENT temp = [ 0 for i in range ( right - left + 1 ) ] NEW_LINE i = left NEW_LINE j = mid + 1 NEW_LINE k = 0 NEW_LINE cnt = 0 NEW_LINE while ( i <= mid and j <= right ) : NEW_LINE INDENT if ( v [ i ] <= v [ j ] ) : NEW_LINE INDENT temp [ k ] = v [ i ] NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT inversions += ( mid - i + 1 ) NEW_LINE temp [ k ] = v [ j ] NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT while ( i <= mid ) : NEW_LINE INDENT temp [ k ] = v [ i ] NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT while ( j <= right ) : NEW_LINE INDENT temp [ k ] = v [ j ] NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT k = 0 NEW_LINE for a in range ( left , right + 1 , 1 ) : NEW_LINE INDENT v [ a ] = temp [ k ] NEW_LINE k += 1 NEW_LINE DEDENT DEDENT def mergeSort ( v , left , right , inversions ) : NEW_LINE INDENT if ( left < right ) : NEW_LINE INDENT mid = ( left + right ) // 2 NEW_LINE mergeSort ( v , left , mid , inversions ) NEW_LINE mergeSort ( v , mid + 1 , right , inversions ) NEW_LINE merge ( v , left , mid , right , inversions ) NEW_LINE DEDENT DEDENT def CountInversions ( v ) : NEW_LINE INDENT n = len ( v ) NEW_LINE inversions = 0 NEW_LINE mergeSort ( v , 0 , n - 1 , inversions ) NEW_LINE return inversions NEW_LINE DEDENT def getSubsCount ( input ) : NEW_LINE INDENT n = len ( input ) NEW_LINE nums = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT nums [ i ] = ord ( input [ i ] ) - 48 NEW_LINE if ( nums [ i ] == 0 ) : NEW_LINE INDENT nums [ i ] = - 1 NEW_LINE DEDENT DEDENT pref = [ 0 for i in range ( n ) ] NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += nums [ i ] NEW_LINE pref [ i ] = sum NEW_LINE DEDENT cnt = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( pref [ i ] > 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT pref = pref [ : - 1 ] NEW_LINE inversions = CountInversions ( pref ) NEW_LINE ans = cnt + inversions + 1 NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT input = "101" NEW_LINE ans = getSubsCount ( input ) NEW_LINE print ( ans ) NEW_LINE DEDENT