Count subsequences 01 in string generated by concatenation of given numeric string K times | C ++ program for the above approach ; Function to calculate the number of subsequences of "01" ; Store count of 0 ' s ▁ and ▁ 1' s ; Count of subsequences without concatenation ; Case 1 ; Case 2 ; Return the total count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubsequence ( string S , int N , int K ) { int C = 0 , C1 = 0 , C0 = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( S [ i ] == '1' ) C1 ++ ; else if ( S [ i ] == '0' ) C0 ++ ; } int B1 = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( S [ i ] == '1' ) B1 ++ ; else if ( S [ i ] == '0' ) C = C + ( C1 - B1 ) ; } int ans = C * K ; ans += ( C1 * C0 * ( ( ( K ) * ( K - 1 ) ) / 2 ) ) ; return ans ; } int main ( ) { string S = "230013110087" ; int K = 2 ; int N = S . length ( ) ; cout << countSubsequence ( S , N , K ) ; return 0 ; }