Sum of the shortest distance between all 0 s to 1 in given binary string | Function to find the total sum of the shortest distance between every 0 to 1 in a given binary string ; Stores the prefix distance and suffix distance from 0 to 1 ; Stores the current distance from 1 to 0 ; Marks the 1 ; If current character is 1 ; Mark haveOne to true ; Assign the cnt to 0 ; Assign prefixDistance [ i ] as 0 ; If haveOne is true ; Update the cnt ; Update prefixDistance [ i ] ; Assign prefixDistance [ i ] as INT_MAX ; Assign haveOne as false ; If current character is 1 ; Mark haveOne to true ; Assign the cnt to 0 ; Assign the suffixDistance [ i ] as 0 ; If haveOne is true ; Update the cnt ; Update suffixDistance [ i ] as cnt ; Assign suffixDistance [ i ] as INT_MAX ; Stores the total sum of distances between 0 to nearest 1 ; If current character is 0 ; Update the value of sum ; Print the value of the sum ; Driver Code
INT_MAX = 2147483647 NEW_LINE def findTotalDistance ( S , N ) : NEW_LINE INDENT prefixDistance = [ 0 for _ in range ( N ) ] NEW_LINE suffixDistance = [ 0 for _ in range ( N ) ] NEW_LINE cnt = 0 NEW_LINE haveOne = False NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT if ( S [ i ] == '1' ) : NEW_LINE INDENT haveOne = True NEW_LINE cnt = 0 NEW_LINE prefixDistance [ i ] = 0 NEW_LINE DEDENT elif ( haveOne ) : NEW_LINE INDENT cnt = cnt + 1 NEW_LINE prefixDistance [ i ] = cnt NEW_LINE DEDENT else : NEW_LINE INDENT prefixDistance [ i ] = INT_MAX NEW_LINE DEDENT DEDENT haveOne = False NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( S [ i ] == '1' ) : NEW_LINE INDENT haveOne = True NEW_LINE cnt = 0 NEW_LINE suffixDistance [ i ] = 0 NEW_LINE DEDENT elif ( haveOne ) : NEW_LINE INDENT cnt = cnt + 1 NEW_LINE suffixDistance [ i ] = cnt NEW_LINE DEDENT else : NEW_LINE INDENT suffixDistance [ i ] = INT_MAX NEW_LINE DEDENT DEDENT sum = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT if ( S [ i ] == '0' ) : NEW_LINE INDENT sum += min ( prefixDistance [ i ] , suffixDistance [ i ] ) NEW_LINE DEDENT DEDENT print ( sum ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = "100100" NEW_LINE N = len ( S ) NEW_LINE findTotalDistance ( S , N ) NEW_LINE DEDENT