Sum of the shortest distance between all 0 s to 1 in given binary string | Java program for the above approach ; 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
import java . io . * ; public class GFG { static void findTotalDistance ( String S , int N ) { int [ ] prefixDistance = new int [ N ] ; int [ ] suffixDistance = new int [ N ] ; int cnt = 0 ; boolean haveOne = false ; for ( int i = 0 ; i < N ; ++ i ) { if ( S . charAt ( i ) == '1' ) { haveOne = true ; cnt = 0 ; prefixDistance [ i ] = 0 ; } else if ( haveOne ) { cnt ++ ; prefixDistance [ i ] = cnt ; } else prefixDistance [ i ] = Integer . MAX_VALUE ; } haveOne = false ; for ( int i = N - 1 ; i >= 0 ; -- i ) { if ( S . charAt ( i ) == '1' ) { haveOne = true ; cnt = 0 ; suffixDistance [ i ] = 0 ; } else if ( haveOne ) { cnt ++ ; suffixDistance [ i ] = cnt ; } else suffixDistance [ i ] = Integer . MAX_VALUE ; } int sum = 0 ; for ( int i = 0 ; i < N ; ++ i ) { if ( S . charAt ( i ) == '0' ) { sum += Math . min ( prefixDistance [ i ] , suffixDistance [ i ] ) ; } } System . out . print ( sum ) ; } public static void main ( String [ ] args ) { String S = "100100" ; int N = S . length ( ) ; findTotalDistance ( S , N ) ; } }