C++ Elegant Prefix Sum Well Explained
Remember that answer can be maximum of 2n/2 moves.\nThat is for each element - maximum of 2 moves\nIt is not possible to get sum={1,0};\nRange of sum is 2 to 2l
Remember that answer can be maximum of 2*n/2 moves.\nThat is for each element - maximum of 2 moves\nIt is not possible to get sum={1,0};\nRange of sum is 2 to 2*limit\n\n```\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int limit) {\n        int n = nums.size();\n        map<int,int> allsums;  //Count all sums \n        for(int i=0;i<nums.size()/2;i++){\n            allsums[nums[i]+nums[n-i-1]]++;\n        }\n        vector<int> omove(2*limit+2,0),tmove(2*limit+2,0);  //Maximum sum possible is 2*limit and minimum sum = 2\n        \n        for(int i=0;i<n/2;i++){\n            int mis = min(nums[i],nums[n-i-1]) + 1;  // If pair is 2,3 and limit=5 - In one move this pair can acheive sum from 3 to 8\n            int mas = max(nums[i],nums[n-i-1]) + limit;  // mis = 3, mas = 8\n            omove[mis]++;      // mark omove[3]=1 and \n            omove[mas+1]--;    // omove[9] = -1 \n            tmove[mas+1]++;     //Now rest of the range takes 2 moves always no matter what\n            tmove[2*limit+1]--; // i.e 2 to 2 and 9 to 10(2*limit)\n            tmove[2]++;      // Do the same in tmove\n            tmove[mis]--;\n        }        \n        //Continuing with above ex, omove[3]=1 and omove[9] = -1\n        // Cummulative sum will make all elements from 3 to 8 as 1 i.e there is one pair which will make this sum\n        // In summary every element of the array will tell how many pairs require one move to get required sum in omove\n        // Same in tmove (i.e 2 moves)\n        for(int i=1;i<omove.size();i++){\n            omove[i]+=omove[i-1];\n            tmove[i]+=tmove[i-1];\n        }\n        // In omove we have to remove sums that have already been acheived i.e in omove we have counted 5 (2+3). Remove that\n        for(auto i:allsums){            \n            omove[i.first]-=i.second;\n        }                \n        int mm=INT_MAX;\n        // min(Sum of omve and 2*tmove) is answer :)\n        for(int i=2;i<omove.size()-1;i++){            \n            mm = min(omove[i]+2*tmove[i],mm);\n        }\n        return mm;\n    }\n};\n```
[]