[C++] Logic for O(n^2) to O(n) explained
The most straightforward solution is this one:\n\nvector<int> minOperations(string boxes) {\n\tint len=boxes.size();\n\tvector<int> minOps(len,0);\n\tfor(int i=
The most straightforward solution is this one:\n```\nvector<int> minOperations(string boxes) {\n\tint len=boxes.size();\n\tvector<int> minOps(len,0);\n\tfor(int i=0; i<len; i++)\n\t\tfor(int j=0; j<len; j++)\n\t\t\tif(boxes[j]==\'1\')\n\t\t\t\tminOps[i]+=abs(i-j);\n\treturn minOps;\n}\n```\nEach ball  at ```boxes[j]``` will take ```abs(i-j)``` to move to ```boxes[i]```. This easily makes for a solution using a nested for loop, but this runs at O(n^2) time complexity. \n\nWe can do better, but we must delve deeper into the logic and take a hard look at what\'s happening. \nWe can say the number of operations at index i can be determined by\n```\n(i*runCnt-prejSum)+(postjSum-i*afterCnt)\n```\n```runCnt``` : the number of balls encountered up till ```i```\n```afterCnt```: the number of balls after ```i```\n```prejSum```: the sum of all indices of balls up to ```i```\n```postjSum```: the sum of all indices of balls after ```i```\n\nIf you don\'t see it right away, take a look at this example, assuming j are the indices of \'1\'\n```boxes = "1101"```\n```\n[sum(abs(0-j)), sum(abs(1-j)), sum(abs(2-j)), sum(abs(3-j))] \n[(0-0) + (1-0)+(3-0) , (1-0)+(1-1) + (3-1) , (2-0)+(2-1) + (3-2) , (3-0)+(3-1)+(3-3)] =\n[(0*1-sum(j<=0)) + (sum(j>0)-0*2), (1*2-sum(j<=1) + (sum(j>1)-1*1), ...]\n[4,3,4,5]\n```\nHopefully that makes it more clear.\n\nWe must do two passes in order to do this in O(n), one to find the total numbers of balls and the sum of all indices where there are balls, and one pass where we use those and some running sums to compute ```numOps[i]```\n\nHere\'s the code using this method (with some algebra and bit shifting marginally optimizing the formula):\n```\nvector<int> minOperations(string boxes) {\n\tint len=boxes.size(), runCnt=0,posSum=0,count=0,totalPosSum=0;\n\tvector<int> minOps(len);\n\tfor(int i=0; i<len; i++)\n\t\tif(boxes[i]==\'1\'){\n\t\t\tcount++;\n\t\t\ttotalPosSum+=i;\n\t\t}\n\tfor(int i=0; i<len; i++){\n\t\tif(boxes[i]==\'1\'){\n\t\t\trunCnt++;\n\t\t\tposSum+=i;\n\t\t}\n\t\t// minOps[i]=(i*runCnt-posSum)+((totalPosSum-posSum)-i*(count-runCnt));\n\t\tminOps[i]=i*((runCnt<<1)-count)+totalPosSum-(posSum<<1);\n\t}\n\treturn minOps;\n}\n```\nDrop any questions, comments, or optimizations of these methods below!
['C', 'C++']