Minimize swaps of adjacent characters to sort every possible rearrangement of given Binary String | Python3 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
MOD = 10 ** 9 + 7 NEW_LINE MEM = [ 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 2048 , 4096 ] NEW_LINE def mod_pow2 ( n ) : NEW_LINE INDENT while n >= len ( MEM ) : NEW_LINE INDENT MEM . append ( ( MEM [ - 1 ] * 2 ) % MOD ) NEW_LINE DEDENT return MEM [ n ] NEW_LINE DEDENT def inversions ( bstr ) : NEW_LINE INDENT total , zeros , questions = ( 0 , ) * 3 NEW_LINE for x in reversed ( bstr ) : NEW_LINE INDENT if x == '1' : NEW_LINE INDENT z = zeros * mod_pow2 ( questions ) NEW_LINE if questions == 0 : NEW_LINE INDENT q = 0 NEW_LINE DEDENT else : NEW_LINE INDENT q = questions * mod_pow2 ( questions - 1 ) NEW_LINE DEDENT total = ( total + z + q ) % MOD NEW_LINE DEDENT elif x == '0' : NEW_LINE INDENT zeros += 1 NEW_LINE DEDENT else : NEW_LINE INDENT total *= 2 NEW_LINE z = zeros * mod_pow2 ( questions ) NEW_LINE if questions == 0 : NEW_LINE INDENT q = 0 NEW_LINE DEDENT else : NEW_LINE INDENT q = questions * mod_pow2 ( questions - 1 ) NEW_LINE DEDENT total = ( total + z + q ) % MOD NEW_LINE questions += 1 NEW_LINE DEDENT DEDENT return total NEW_LINE DEDENT def main ( ) : NEW_LINE INDENT S = " ? 0 ? " NEW_LINE print ( inversions ( S ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT main ( ) NEW_LINE DEDENT