Minimize swaps of adjacent characters to sort every possible rearrangement of given Binary String | Javascript 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 ; Given string S ; Function Call
let MOD = 1000000007 ; let MEM = [ 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 2048 , 4096 ] ; function mod_pow2 ( n ) { while ( n >= MEM . length ) MEM . push ( ( MEM [ MEM . length - 1 ] * 2 ) % MOD ) ; return MEM [ n ] ; } function inversions ( bstr ) { let total = 0 , zeros = 0 , questions = 0 ; bstr . reverse ( ) ; for ( let i = 0 ; i < bstr . length ; i ++ ) { let q ; if ( bstr [ i ] == ' ' ) { let z = zeros * mod_pow2 ( questions ) ; if ( questions == 0 ) q = 0 ; else q = questions * mod_pow2 ( questions - 1 ) ; total = ( total + z + q ) % MOD ; } else if ( bstr [ i ] == ' ' ) { zeros += 1 ; } else { total *= 2 ; let 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 ; } let S = " " . split ( ' ' ) ; document . write ( inversions ( S ) ) ;