1769: Minimum-Number-of-Operations-to-Move-All-Balls-to-Each-Box
Medium
table of contents
Prefix Sum might just be the name of the game.
My algorithm stems from the fact that each answer[i]
is related to answer[i-1] and answer[i+1] (if they exist). What I
mean by this, is that, since each answer[i]
is related
towards the relative position of each ball and the relative
position of each ball does not change, when we iterate
through each answer[i]
, we find that we can calculate
answer[i+1]
using our answers from the previous index
answer[i]
.
For example, our answer[i]
value depends on the
n
balls that we have passed, and the m
balls
that we have not passed yet. When we calcualte answer[i+1]
,
we find that it is simply just answer[i] + n - m
(as each
of the n
balls gets 1 box
further, and each of
the m
balls gets 1 box
closer).
Using this logic, we can just iterate through the boxes
string to find our answer for answer[0]
, and use it to
calculate the rest of the values inside answer
.
code
class Solution {
public:
<int> minOperations(string boxes) {
vectorint balls = 0;
<int> ans;
vectorint curr = 0;
for (int i = 0; i < boxes.size(); ++i) {
+= boxes[i]-'0';
balls += (boxes[i]-'0')*i;
curr }
int passed = 0;
.push_back(curr);
ans+= boxes[0]-'0';
passed for (int i = 1; i < boxes.size(); ++i) {
+= passed;
curr -= balls-passed;
curr .push_back(curr);
ans+= boxes[i]-'0';
passed }
return ans;
}
};