Minimize swaps of adjacent characters to sort every possible rearrangement of given Binary String | C ++ program for the above approach ; Precalculate the values of power of 2 ; Function to calculate 2 ^ N % mod ; Function to find sum of inversions ; Initialise a list of 0 s and ? s ; Traverse the string in the reversed manner ; If the current character is 1 ; Effectively calculate a * b ^ ( b - 1 ) ; If the current character is 0 ; Increment count of zeroes ; Double count the zeroes ; Find b * 2 ^ ( b - 1 ) ; Increment count of questions ; Return the final count ; Driver Code ; Given string S ; Function Call
#include <bits/stdc++.h> NEW_LINE #define MOD  1000000007 NEW_LINE using namespace std ; vector < int > MEM = { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 2048 , 4096 } ; int mod_pow2 ( int n ) { while ( n >= MEM . size ( ) ) MEM . push_back ( ( MEM [ -1 ] * 2 ) % MOD ) ; return MEM [ n ] ; } int inversions ( string bstr ) { int total = 0 , zeros = 0 , questions = 0 ; reverse ( bstr . begin ( ) , bstr . end ( ) ) ; for ( char x : bstr ) { int q ; if ( x == '1' ) { int z = zeros * mod_pow2 ( questions ) ; if ( questions == 0 ) q = 0 ; else q = questions * mod_pow2 ( questions - 1 ) ; total = ( total + z + q ) % MOD ; } else if ( x == '0' ) { zeros += 1 ; } else { total *= 2 ; int z = zeros * mod_pow2 ( questions ) ; if ( questions == 0 ) q = 0 ; else q = questions * mod_pow2 ( questions - 1 ) ; total = ( total + z + q ) % MOD ; questions += 1 ; } } return total ; } int main ( ) { string S = " ? 0 ? " ; cout << inversions ( S ) ; }