- binary-string, Blogathon, Blogathon-2021, Greedy, Mathematical, Strings

Sum of the shortest distance between all 0s to 1 in given binary string

#include using namespace std;void findTotalDistance(string S, int N){            vector prefixDistance(N);    vector suffixDistance(N);            int cnt = 0;        bool haveOne = false;    for (int i = 0; i < N; ++i) {                if (S[i] == '1') {                        haveOne = true;                        cnt = 0;                        prefixDistance[i] = 0;        }                else if (haveOne) {                        cnt++;                        prefixDistance[i] = cnt;        }                        else            prefixDistance[i] = INT_MAX;    }        haveOne = false;    for (int i = N - 1; i >= 0; –i) {                if (S[i] == ‘1’) {                        haveOne = true;                        cnt = 0;                                    suffixDistance[i] = 0;        }                else if (haveOne) {                        cnt++;                                    suffixDistance[i] = cnt;        }        else                                    suffixDistance[i] = INT_MAX;    }            int sum = 0;    for (int i = 0; i < N; ++i) {                if (S[i] == '0') {                        sum += min(prefixDistance[i],                       suffixDistance[i]);        }    }        cout