Count of substrings in a Binary String that contains more 1 s than 0 s | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void merge ( vector < int > & v , int left , int mid , int right , int & inversions ) { vector < int > temp ( right - left + 1 ) ; int i = left ; int j = mid + 1 ; int k = 0 ; int cnt = 0 ; while ( i <= mid && j <= right ) { if ( v [ i ] <= v [ j ] ) { temp [ k ++ ] = v [ i ++ ] ; } else { inversions += ( mid - i + 1 ) ; temp [ k ++ ] = v [ j ++ ] ; } } while ( i <= mid ) temp [ k ++ ] = v [ i ++ ] ; while ( j <= right ) temp [ k ++ ] = v [ j ++ ] ; k = 0 ; for ( int a = left ; a <= right ; a ++ ) { v [ a ] = temp [ k ++ ] ; } } void mergeSort ( vector < int > & v , int left , int right , int & inversions ) { if ( left < right ) { int mid = ( left + right ) / 2 ; mergeSort ( v , left , mid , inversions ) ; mergeSort ( v , mid + 1 , right , inversions ) ; merge ( v , left , mid , right , inversions ) ; } } int CountInversions ( vector < int > & v ) { int n = v . size ( ) ; int inversions = 0 ; mergeSort ( v , 0 , n - 1 , inversions ) ; return inversions ; } int getSubsCount ( string & input ) { int n = input . length ( ) ; vector < int > nums ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { nums [ i ] = input [ i ] - '0' ; if ( nums [ i ] == 0 ) nums [ i ] = -1 ; } vector < int > pref ( n ) ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += nums [ i ] ; pref [ i ] = sum ; } int cnt = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( pref [ i ] > 0 ) cnt ++ ; } reverse ( pref . begin ( ) , pref . end ( ) ) ; int inversions = CountInversions ( pref ) ; int ans = cnt + inversions ; return ans ; } int main ( ) { string input = "101" ; int ans = getSubsCount ( input ) ; cout << ans << endl ; return 0 ; }