human
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"
Solution in Python:
assistant
#Here is code to count of substrings in a Binary String that contains more 1 s than 0 s and the other steps required.
 def merge ( v , left , mid , right , inversions ) :
	temp = [ 0 for i in range ( right - left + 1 ) ]
	i = left
	j = mid + 1
	k = 0
	cnt = 0
	while ( i <= mid and j <= right ) :
		if ( v [ i ] <= v [ j ] ) :
			temp [ k ] = v [ i ]
			k += 1
			i += 1
		else :
			inversions += ( mid - i + 1 )
			temp [ k ] = v [ j ]
			k += 1
			j += 1
	while ( i <= mid ) :
		temp [ k ] = v [ i ]
		k += 1
		i += 1
	while ( j <= right ) :
		temp [ k ] = v [ j ]
		k += 1
		j += 1
	k = 0
	for a in range ( left , right + 1 , 1 ) :
		v [ a ] = temp [ k ]
		k += 1
def mergeSort ( v , left , right , inversions ) :
	if ( left < right ) :
		mid = ( left + right ) // 2
		mergeSort ( v , left , mid , inversions )
		mergeSort ( v , mid + 1 , right , inversions )
		merge ( v , left , mid , right , inversions )
def CountInversions ( v ) :
	n = len ( v )
	inversions = 0
	mergeSort ( v , 0 , n - 1 , inversions )
	return inversions
def getSubsCount ( input ) :
	n = len ( input )
	nums = [ 0 for i in range ( n ) ]
	for i in range ( n ) :
		nums [ i ] = ord ( input [ i ] ) - 48
		if ( nums [ i ] == 0 ) :
			nums [ i ] = - 1
	pref = [ 0 for i in range ( n ) ]
	sum = 0
	for i in range ( n ) :
		sum += nums [ i ]
		pref [ i ] = sum
	cnt = 0
	for i in range ( n ) :
		if ( pref [ i ] > 0 ) :
			cnt += 1
	pref = pref [ : - 1 ]
	inversions = CountInversions ( pref )
	ans = cnt + inversions + 1
	return ans
if __name__ == ' _ _ main _ _ ' :
	input = "101"
	ans = getSubsCount ( input )
	print ( ans )