Prefix Sum C++ with Explain
Brute & Force (Accepted)\n#### Idea\nFor every element i in boxes, we travel the whole array and count the distance from element i to j, if boxes[j] == \'1\'.\n
### Brute & Force (Accepted)\n#### Idea\nFor every element `i` in `boxes`, we travel the whole array and count the distance from element `i` to `j`, if `boxes[j] == \'1\'`.\n#### Time Complexity\nO(n^2)\n> Notice that this solution is accepted because the size of test data is small (2000). Generally this method may cause TLE when the size of test data is in 10^4 or larger.\n\n#### Code\n```cpp\nclass Solution {\npublic:\n    vector<int> minOperations(string boxes) {\n        int n = boxes.size();\n        vector<int> ans;\n        for(int i = 0; i < n; i++)\n        {\n            int res = 0;\n            for(int j = 0; j < n; j++)\n            {\n                if(boxes[j] == \'1\')\n                {\n                    res += abs(i-j);\n                }\n            }\n            ans.push_back(res);\n        }\n        return ans;\n    }\n};\n```\n### Prefix Sum\n#### Idea\nIn above, we traveled the whole array for every element. But actually, things could be easier.\nLet\'s consider the following situation: we have handled the `i`th element and we have known that the answer is `answer[i]`, i.e., **the minimum number of operations to move all balls to box `i` is `answer[i]`**.    \n\nNotice that, when the pointer moves to `i+1`, if there are `cntl` `\'1\'`s in the left of `i+1` (i.e., [0, i]), the total cost will be added by `cntl` compared with `x`. That\'s beacuse you need to move all of them further by 1. Similarily, when the pointer moves to `i+1`, if there are `cntr` `\'1\'`s in the right of `i` (i.e., [i+1, n-1]), the total cost will be subtracted  by `cntr`.  That\'s because you can move them to `i+1` in a less cost compared with moving them to `i`. \n\nHence, we have `answer[i+1] = answer[i] + cntl - cntr`. \nAnd that\'s the key. \n\n#### Time Complexity\nO(n)\n\n### Code\n\n```cpp\nclass Solution {\npublic:\n    vector<int> minOperations(string bs) {\n        int n = bs.size();\n\t\t\n\t\t// We use l[i] to record there are how many 1s before index i\n\t\t// and r[i] to record there are how many 1s after index i, including i.\n        vector<int> l(n, 0), r(n + 1, 0), ans(n, 0);\n\t\t\n\t\t// Initialisation of l\n\t\t// With out loss of generality, we can count the answer for index 0 and deduce other answers based on answer[0]\n\t\t// We count answer[0] simultaneously here\n        for(int i = 1; i < n; i++)\n        {\n            if(bs[i-1] == \'1\')\n            {\n                l[i] = l[i-1] + 1;\n                ans[0] += i-1;\n            }\n            else\n                l[i] = l[i-1]; \n        }\n        if(bs[n-1] == \'1\')ans[0] += n - 1;\n\n\t\t// Initialisation of r\n        for(int i = n - 1; i >= 0; i --)\n        {\n            if(bs[i] == \'1\') r[i] = r[i+1] + 1;\n            else r[i] = r[i+1];\n        }\n\n        for(int i = 1; i < n; i++)\n        {\n            ans[i] = ans[i - 1] + l[i] - r[i];\n        }\n\n        return ans;\n    }\n};\n```
['C']